**CS-507A: Computational Geometry**

*"Geometry will draw the soul towards truth."
*- Plato

**For detailed course contents
and reading material on the topics listed below see the Web
Reading Material**

**Course Contents:**

**Classical Geometry and Basic
Concepts**

- The straight-edge and compass
- Constructive geometry of the Greeks
- Modern complexity theory
- Polygons and representations
- The area of a triangle as a computational primmitive

**Point Inclusion Problems**

- The Jordan curve theorem
- The plumb-line algorithm
- Point inclusion in the query mode

**Convexity Testing**

- Simple polygons
- Crossing polygons

**Polygon Triangulation**

- The two-ears theorem
- Diagonal insertion
- Finding an ear in linear time

**Distances Within and Between
Sets**

- Minkowski metrics
- Diameter algorithms
- The two-coins algorithm
- The rotating calipers algorithm
- Computing the maximum distance between two sets
- Computing the minimum distance between two sets

**Triangulations of Points**

- Triangulation via Polygonizations of points
- Divide-and-conquer
- The three-coins algorithm
- Monotone polygons
- Star-shaped polygons
- Edge-visible polygons
- Externally visible polygons

**Art-Gallery Theorems**

- Chvatal's art gallery theorem
- Three-colorability of triangulated polygons
- Point guards
- Movable guards

**Complexity, Convexity and Unimodality**

- Unimodal distance functions in geometry
- Prune-and-search problems

**Convex Hulls**

- Convex hull algorithms for points in the plane
- Convex hull algorithms for polygons
- The Jarvis march
- The Graham scan
- Linear expected time algorithms
- The throw-away principle
- Convex hulls in 3 dimensions

**Hidden-Line Problems**

- Visibility from a point
- Visibility from an edge
- Visibility from a line

**Updating Triangulations of Points
and Line Segments**

- Inserting and deleting points
- Inserting and deleting edges

**Intersection Problems**

- Intersecting convex polygons
- Intersecting half-planes
- Intersecting simple polygons

**Proximity Graphs**

- Minimal spanning trees
- Nearest neighbour graphs
- The relative neighbourhood graph
- The Gabriel graph
- The Delaunay triangulation and Voronoi diagram
- Sphere of influence graphs

**Linear Programming**

- Linear programming problems in geometry
- Megiddo's linear time algorithm
- Applications of linear programming

**Facility Location**

- The minimax facility location problem
- The smallest enclosing circle
- Generalisations to geodesic metrics
- Megiddo's linear time algorithm

**Movable Separability of Objects**

- Translation separability of objects
- Geodesic convex hulls
- Shortest-path algorithms
- The algorithm of Chazelle and Lee-Preparata

**Removing Non-Degeneracy Assumptions**

- No two points on a vertical line
- No three points on a vertical plane
- No two points with the same coordinates

**Transversals of Sets**

- The Philon line
- Point-line duality and the space of transversals
- Computing shortest transversals

**Arrangements**

- Arrangements of lines
- Arrangements of line segments
- Envelopes of arrangements of lines
- Arrangements of discs
- Arrangements of Jordan curves

**Skeletons of Polygons**

- The medial axis
- The straight-line skeleton

**Visualization**

- Nice projections
- Map projections
- Regular projections and knot theory
- Aperture-angle optimization problems
- The spindle torus
- Kepler's apples and lemons
- More about Kepler