[Please remove <h1>]

---

Objectives

To provide the student with an introduction to the design, analysis, and application of algorithms for geometric problems. Students are expected to have basic knowledge of algorithm design and analysis.

References

Computational Geometry: Algorithms and Applications, by de Berg, van Kreveld, Overmars, and Schwarzkopf, Springer-Verlag, 1997.

Schedule

Three hours of lecture per week.

Outline

Convexity (9 hrs)

Convex hull algorithms in two dimensions. Point-line duality. Applications. Convex polyhedra and convex hull algorithms in three dimensions.

Proximity of Points (6 hrs)

Voronoi diagrams and Delaunay triangulations. Connection to convex hulls. Applications: nearest neighbors, minimum spanning trees.

Geometric Optimization (6 hrs)

Linear programming in low dimensions. Prune-and-search and randomized search techniques.

Line Segments, Planar Subdivisions, and Polygons (9 hrs)

Intersection and arrangement of line segments. Plane-sweep and randomized incremental algorithms. Segment trees. Point location data structures. Triangulation of simple polygons. Other problems for polygons: decomposition, visibility, motion planning.

Range Searching (6 hrs)

Orthogonal range trees. Ham-sandwich cuts and partition trees. Random sampling and epsilon-cutting.