CS 5960/6961 Computational Geometry
Fall 2003

Instructor: Emil Praun
Location: MEB 3105
Time: TTh 12:25-1:45
Textbook: "Computational Geometry: Algorithms and Applications", 2nd ed., M. de Berg et al., Springer

Project due 12/5.
Assignment 2 due 11/13 before class.
Assignment 1 due 9/23 before class.

Grading

• 15% class participation, 45% assignments, 40% exams
• Collaboration policy: no collaboration. You should try to figure out the problems on your own, without consulting other people in the class or outside sources.
• Late policy: -10% / late day. You have to turn in all assignment to pass the class (even if they are > 10 days late).

Syllabus

• Introduction
• 2D Convex Hulls
  • Brute force, Jarvis march, Quick hull, Monotone march, Graham scan, "Ultimate" convex hull (Kirckpatrick-Seidel) (cache)
    • O(n) deterministic median finding (cache)
• 3D Convex Hulls
  • Divide and Conquer, Incremental algorithm
• Line segment intersection; Map overlay
• Art Gallery theorem; Polygon triangulation
• Range queries (k-d trees, range trees, fractional cascading [cache])
• Point location
• Voronoi diagram, Delaunay triangulation
• Graph embedding (Colin de Verdiere's proof of Tutte's theorem)
• Windowing queries (interval / priority search / segment trees)
• Minkowski sums