# 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.