CIS 677: Computational Geometry and Applications

Lectures: Monday, Wednesday 10:30 - 12:00, Towne 321

Office Hours: By Appointment

Theory: Combinatorial Duality, Arrangements, Combinatorics, Triangulations, Zone theorems, Cuttings, e-nets, VC dimension, Incidences, Davenport Schinzel Sequences Algorithmic Range Searching, topological sweep, vertical decompositions, fractional cascading, incremental constructions, parametric search, fixed dimension linear programming, Lower bounds etc.

Applications: Range searching/Point Location, Covering, GIS Terrain, etc. Motion Planning, Localization, Art Gallery, Watchman and evasion problems, etc. BSP, Visibility Graphs, Visibility, Hardware, Collision detection etc. Plus any other depending on student interest and time.

Lecture Notes

1. Lecture 1 (1/13): History of Computational Geometry. Convex Hulls.
   Useful Links:
   • Euclid's Elements. Highly browsable
   • A nice applet demonstrating Graham Scan and the Jarvis March
2. Lecture 2 (1/15): Convex Hulls, continued. Duality.
   Useful links:
   • A Java page demonstrating some of the basic duality transforms.
3. Lecture 3 (1/22): Arrangements, plane sweeps, and the Zone Theorem.
4. Lecture 4 (1/27): Point Location I (Slabs) NEW !!
5. Lecture 5 (1/29): Point Location II (Incremental Constructions)
6. Lecture 6 (2/3): Voronoi Diagrams. Ch. 7 from CG: Algorithms and Applications
   Useful Links:
   • A Java Voronoi Diagram Applet
7. Homework 1
8. Lecture 7 (2/5): Delauney Triangulations. Ch. 9 from CG: Algorithms and Applications
9. Lecture 8 (2/10): Lifting Maps and high-dimensional geometry.
10. Lecture 9 (2/12): Minkowski Sums and Path Planning. Ch 13.3 from CG: Algorithms and Applications.

Resources

Monographs and Surveys:

• Agarwal and Erickson. Geometric range searching and its relatives (1998)

Suggested Books:

• de Berg, van Kreveld, Overmars and Schwarzkopf. Computational Geometry: Algorithms and Applications . Springer-Verlag, 2000 (2nd ed.)
• Edelsbrunner. Algorithms in Combinatorial Geometry, Springer--Verlag, Heidelberg, 1987.
• Pach and Agarwal. Combinatorial Geometry. Wiley and Sons, 1995.

• LEDA: C++ Templates for basic algorithms.
• CGAL: The computational geometry algorithms library.
• The Boost Graph Library

Last Modified: Sun Jan 19 00:18:55 EST 2003