Computational Geometry

Mort Yao

Textbook:

  • Mark de Berg, Marc van Kreveld, Mark Overmars, Otfried Cheong Schwarzkopf. Computational Geometry: Algorithms and Applications, 3rd edition.
  1. Introduction
  2. Line segment intersection
  3. Polygon triangulation
  4. Linear programming
  5. Orthogonal range searching
  6. Point location
  7. Voronoi diagrams
  8. Arrangements and duality
  9. Delaunay triangulations
  10. More geometric data structures
  11. Convex hulls
  12. Binary space partitions
  13. Robot motion planning
  14. Quadtrees
  15. Visibility graphs
  16. Simplex range searching