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

Course Contents:

Classical Geometry and Basic Concepts

1. The straight-edge and compass
2. Constructive geometry of the Greeks
3. Modern complexity theory
4. Polygons and representations
5. The area of a triangle as a computational primmitive

Point Inclusion Problems

1. The Jordan curve theorem
2. The plumb-line algorithm
3. Point inclusion in the query mode

Convexity Testing

1. Simple polygons
2. Crossing polygons

Polygon Triangulation

1. The two-ears theorem
2. Diagonal insertion
3. Finding an ear in linear time

Distances Within and Between Sets

1. Minkowski metrics
2. Diameter algorithms
3. The two-coins algorithm
4. The rotating calipers algorithm
5. Computing the maximum distance between two sets
6. Computing the minimum distance between two sets

Triangulations of Points

1. Triangulation via Polygonizations of points
2. Divide-and-conquer
3. The three-coins algorithm
4. Monotone polygons
5. Star-shaped polygons
6. Edge-visible polygons
7. Externally visible polygons

Art-Gallery Theorems

1. Chvatal's art gallery theorem
2. Three-colorability of triangulated polygons
3. Point guards
4. Movable guards

Complexity, Convexity and Unimodality

1. Unimodal distance functions in geometry
2. Prune-and-search problems

Convex Hulls

1. Convex hull algorithms for points in the plane
2. Convex hull algorithms for polygons
3. The Jarvis march
4. The Graham scan
5. Linear expected time algorithms
6. The throw-away principle
7. Convex hulls in 3 dimensions

Hidden-Line Problems

1. Visibility from a point
2. Visibility from an edge
3. Visibility from a line

Updating Triangulations of Points and Line Segments

1. Inserting and deleting points
2. Inserting and deleting edges

Intersection Problems

1. Intersecting convex polygons
2. Intersecting half-planes
3. Intersecting simple polygons

Proximity Graphs

1. Minimal spanning trees
2. Nearest neighbour graphs
3. The relative neighbourhood graph
4. The Gabriel graph
5. The Delaunay triangulation and Voronoi diagram
6. Sphere of influence graphs

Linear Programming

1. Linear programming problems in geometry
2. Megiddo's linear time algorithm
3. Applications of linear programming

Facility Location

1. The minimax facility location problem
2. The smallest enclosing circle
3. Generalisations to geodesic metrics
4. Megiddo's linear time algorithm

Movable Separability of Objects

1. Translation separability of objects
2. Geodesic convex hulls
3. Shortest-path algorithms
4. The algorithm of Chazelle and Lee-Preparata

Removing Non-Degeneracy Assumptions

1. No two points on a vertical line
2. No three points on a vertical plane
3. No two points with the same coordinates

Transversals of Sets

1. The Philon line
2. Point-line duality and the space of transversals
3. Computing shortest transversals

Arrangements

1. Arrangements of lines
2. Arrangements of line segments
• Envelopes of arrangements of lines
3. Arrangements of discs
4. Arrangements of Jordan curves

Skeletons of Polygons

1. The medial axis
2. The straight-line skeleton

Visualization

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