Personal tools
You are here: Home Courses Algorithmic Robotics and Motion Planning Spring 2011 Computational Geometry Information
« November 2021 »
Log in

Forgot your password?

Computational Geometry Information

If you have not taken the course Computational Geometry, you are encouraged to study by yourself some fundamental concepts, algorithms and data structures in the field. The chapters below refer to the following textbook:

M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf, Computational Geometry: Algorithms and Applications 
2nd Edition, Springer, 2000.

Reading Chapters 1 and 2 is a must. In class it will be assumed that you are familiar with the following: polygon, convexity, convex-hull, plane sweep, DCEL.

Later on, we will use concepts and algorithms from the following chapters: 
Chapter 3 - triangulations 
Chapter 5 - range search 
Chapter 6 - trapezoidal decomposition and point location 
Chapter 7 - Voronoi diagrams

The topic of arrangements will be studied in class.

There are some chapters in the book dedicated or related to motion planning. The contents of these chapters will be covered in class.

Document Actions