**Text Book:** Computational
Geometry in C *by* Joseph O'Rourke

*"Geometry is a skill of the eyes and
the hands as well as the mind." *- Jean Peterson

**Week: 1-2-3-4-5-6-7-8-9-10-11-12-13-14**

- Introduce course
- Models of computation
- Knotted string computer and Pythagoras' Theorem
- Smallest enclosing circle of a set of points
- Web: 1.1.4 - Polygons and representations
- Web: 1.1.5 - Computing the area of a polygon
- Web: 1.6.1 - Notes on methods of proof

- The power of the collapsing compass
- Case analysis in proofs
- The Real RAM (ceiling and floor functions)
- Define polygons (Jordan curve theorem)
- Data structures for polygons (standard form)
- Area of a triangle (polygon)
- Sidedness test, point inclusion in a triangle
- Constructing
a square with the
*Toothpick Computer* - Circles enclosing polygons
- Recognizing if a (possibly crossing) polygon is convex (and simple) in linear time
- Discuss some projects
- Line segment intersection
- Point inclusion
- In a convex polygon
- Query mode in a convex polygon
- Text: 1.3 - Area of a polygon
- Web: 1.1.3 - A New Look at Euclid's Second Proposition (PostScript)
- Web: 2.1 - Jordan curve theorem
- Text: 1.5 - Segment intersection
- Web: 1.1.1 - Applet of Francois Labelle
- Web: 2.1 - Octavian Cismasu's applet

- Point inclusion
- One-shot in convex polygons in O(log n) time
- In a simple polygon
- The plumb-line algorithm
- Query mode for simple polygons
- Testing convexity
- Of simple polygons
- Of crossing polygons
- Maximal vectors, polygons and hulls
- Discuss projects
- Triangulating simple polygons
- Diagonal insertion and induction
- Text: Chapter 1
- Web: 4.2.1 - Ian Garton's tutorial on polygon triangulation
- Web: 4.2.1 - Ian Garton's applets

- Chvatal's art gallery theorem
- Three-coloring triangulated polygons
- The pigeonhole principle
- Star-shaped polygons and fans
- Edge guards
- Two-ears theorem
- Via induction
- Via dual trees
- Triangulating simple polygons in quadratic time
- Convex partitioning of simple polygons
- Polygonizations of point sets
- Monotonic polygonizations
- Star-shaped polygonizations
- Spiral polygonizations
- Enclosing a convex polygon with a triangle
- Midpoint polygonization of points
- Visibility in street-polygons and walkable-polygons
- Text: Chapter 2 - Polygon partitioning
- Web: 5.1.2 - Tutorial on art gallery theorem
- Web: 6.1 - Polygonization tutorial
- Web: 5.1.2 - Thierry Dagnino's applet
- Web: 6.1 - Polygonization applet
- Web: 6.2 - Polygonization counter (applet)

- Diameter of a convex polygon
- Two-coins algorithm
- Multimodality of distance functions
- Antipodal pairs
- Rotating calipers solution to diameter problem
- The width of a set
- Passing a chair through a door
- Smallest enclosing rectangle
- Maximum distance between two convex polygons
- Handout - Multimodality
- Handout - Distance
- Handout - Snyder-Tang algorithm
- Web: 7.1 - Mikowski metrics
- Web: 7.1.1 - Distance
- Web: 7.1.2 - Manhattan metric

- Web: 7.1.2 - Taxicab metric applet
- Web: 7.5.1 - Jaqueline Chen's tutorial on width and line fitting
- Web: 7.6.1 - Rotating caliper page of Hormoz Pirzadeh

- Convex hull algorithms for points in the plane
- Rosenberg and Landgridge
- The Jarvis march (gift wrapping)
- The 3-coins algorithm
- The Graham scan
- Divide and conquer with rotating-caliper merge
- Lower bound
- The throw-away principle
- Convex hulls and triangulations of special polygons with the 3-coins algorithm
- Edge-visible polygons
- Weakly-externally visible polygons
- O(n) time convex hulls of simple polygons
- The Graham-Yao algorithm
- Text: Chapter 3 - Convex hulls in two dimensions
- Handout: the Graham-Yao algorithm
- Web: 10.1 - Convex hull applets

- O(n) time convex hulls of simple polygons
- Melkman's on-line algorithm
- Visibility in polygons
- Edge-visible polygons (weak, strong and complete visibility)
- O(n) algorithm for testing edge visibility (3-coins application)
- Computing the diameter of a polygon
- Computing the diameter of a set of points
- Triangulations, sorting and lower bounds
- Convex hulls of polygons
**Movable separability of sets:**- Balls in space (Dawson's theorem)
- Orthogonal boxes (Guibas-Yao theorem)
- Convex polyhedra
- Star-shaped polygons
- Handout: Melkman's algorithm
- Handout: Edge visibility
- Web: 10.3.1 - Pierre Lang's tutorial on Melkman's algorithm
- Web: 11.2 - Edge visibility
- Text: 8.7 - movable separability of objects
- Web: 17.1 - The match-stick game
- Web: 17.2.1 - Separating objects in space
- Web: 17.2 - Movable separability of objects
- Web: 10.3.1 - Melkman's algorithm applet
- Web: 17.1 - Applet for the match-stick game
- Web: 17.2.1 - Applet for separating star-shaped polygons

- Dawson's theorem on star-shaped bodies
- Dual-tree of a triangulated polygon
- Shortest paths inside polygons
- Relative (geodesic) convex hulls

- Separating 2 simple polygons (finish proof)
- Proof of correctness of 3-coins algorithm
- For triangulating edge-visible polygons
- For convex hull of weakly externally visible polygons
- Applications of 3-coins algorithm
- Triangulating monotonic polygons
- Divide & Conquer algorithm for intersecting half-planes (convex polygons)
- Divide & Conquer algorithm for triangulating sets of points
- Text: Chapter 8, Motion planning
- Text: 7.6 - Intersection of convex polygons
- Web: 13.1.3 - A simple linear algorithm for intersecting convex polygons (same as handout)
- Handout: Sack & Toussaint paper on separability
- Web: 13.1.2 - Eric Plante's tutorial on convex polygon intersection
- Web: 17.4 - Separating two simple polygons by a single translation
- Web: 17.5.3 - Shortest path applet
- Web: 13.1.2 - Applet for convex polygon intersection

- Proximity graphs
- Nearest neighbor graphs
- Minimal spanning trees
- Relative neighborhood graphs
- Gabriel graphs
- Delaunay triangulations
- Computing proximity graphs
- Voronoi diagram algorithms
- Via half-plane intersections
- Rhynsberger's algorithm - O(n^2)
- Text: 5.1 to 5.4 - Voronoi diagrams
- Web: 14.3 - The relative neighborhood graph
- Web: 14.1 - Minimal spanning tree applet
- Web: 14.6.1 - Fantastic applet for Voronoi diagrams and Delaunay triangulations

- Computing proximity graphs (cont.)
- MST-RNG-DT relationships
- Furthest-point Voronoi diagrams
- The diameter of a set and furthest-point Delaunay triangulations
- Proximity graphs via local search of DT
- Bucketing methods for proximity graphs
- Convex hulls in 3 dimensions in O(n log n) time (Preparata & Hong algorithm)
- Translation ordering of rectangles
- Triangulating line segments (induction proof)
- Voronoi diagrams and Delaunay triangulations in 2D via convex hulls in 3D
- Convex hulls in 3 dimensions cont.
- Beneath-beyond method in O(n^2) time
- Voronoi diagrams in 2D via convex hulls in 3D
- Alpha hulls and shapes
- Sphere of influence graph
- Web: 14.9 - Proximity graphs (including a survey paper)
- Text: Chapter 4 - Convex hulls in 3 dimensions
- Web: 14.3 - Relative neighborhood graph
- Web: 14.8 - Sphere-of-influence graph tutorial (Richard Unger)
- Web: 14.8 - Sphere-of-influence graph applet

**Arrangements:**- Arrangements of lines
- Convex hulls of arrangements
- Hamiltonian cycles in arrangement graphs
- Point-line duality
- Computing the space of transversals in O(n log n) time
**Transversals:**- The Philo line
- Relation to doubling the cube
- Characterizations
- Computing shortest transversals of line segments
- Critical support lines
- Intersecting a line with a convex polygon
- Minimum distance between convex polygons
- Computing shortest transversals of lines
- The envelope of an arrangement
- Web: 14.11.1 - Alpha-shape tutorial of Francois Belair
- Text: 6.1-6.5 - Arrangements and duality
- Handout: Computing shortest transversals
- Web: 14.11.1 - Alpha-shape applet
- Web: 19.2.1 - Duality applets

**Triangulations revisited:**- Finding an ear in linear time with prune-and-search
- Efficient practical polygon triangulation
- Modified Graham scan
- Sleeve-searching algorithm
- Updating triangulations
- Inserting and deleting vertices
- Inserting and deleting edges
- Arrangements of lines
- Facility location
- Removing degeneracies in computational geometry
- Intrinsic and algorithm-induced degeneracies
- No two points on a vertical line in 2 and 3 dimensions
- Decision, computation and optimization problem
- Lower bound via element-uniqueness
- Web: 4.1 - History of polygon triangulation
- Web: 4.4 - Finding an ear with prune-and-search
- Web: 4.5 - Modified Graham scan
- Web: 12 - Tutorial on updating triangulations of points and line segments
- Handout: Output-complexity sensitive polygon triangulation
- Web: 18.1-4 and 18.7 - Removing degeneracies
- Web: 4.4 - Modified Graham scan applet of Ian Garton
- Web: 12 - Updating triangulations applets

**Problem Assignment #5**

- Degeneracies cont.
- Smallest spherical cap containing n points
- No two points with the same x, y or z coordinates.
- Linear programming in linear time (Meggido's algorithm)
- Linear median finding algorithm of Blum, Floyd, Pratt, Rivest & Tarjan
- Smallest enclosing circle in linear time (Meggido's algorithm)
- Smallest spherical cap containing a set of points
- On a sphere
- On a hemisphere
- Web: Chapter 16 - Facility location
- Web: Chapter 16 applets

**Problem Assignment #5 due****Entire Web Project including Java Applet due December 9th.**