**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
- The straight-edge-and-compass computer
- The tooth-pick computer
- Review projects
- Constructing
a square with the
*Toothpick Computer* - Circles enclosing polygons
- Recognizing if a (possibly crossing) polygon is convex (and simple) in linear time
- Review more projects
- The Real RAM (ceiling and floor functions)
- Define polygons (Jordan curve theorem)
- Data structures for polygons (standard form)
- Area of a triangle (of a polygon)
- Sidedness test, point inclusion in a triangle (in a convex polygon)
- Segment intersection test
- Text: 1.3 - Area of a polygon
- Web: 1.4 - Polygons and representations
- Web: 1.5 - Computing the area of a polygon
- Web: 1.6.1 - Notes on methods of proof
- Web: 1.6.2 - Notes on how to do proofs
- 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

- Discuss projects
- Chvatal's art gallery theorem
- Fisk's proof
- Point inclusion continued
- Queries in O(log n) time
- Discuss projects
- Point inclusion continued
- In a simple polygon
- The plumb-line algorithm
- Query mode for simple polygons
- Smallest enclosing circle
- Brute force algorithm
- Testing convexity
- Of simple polygons
- Text: Chapter 1
- Web: 3.1-3.3 - Testing the orientation and convexity of a polygon
- Web: 4.2.1 - Ian Garton's tutorial on polygon triangulation
- Web: 4.2.1 - Ian Garton's applets

- Two-ears theorem
- Via induction
- Via dual trees
- Triangulating simple polygons
- Via ear-cutting
- Via diagonal insertion
- Convex partitioning of simple polygons
- Polygonizations of point sets
- Maximal vectors
- Monotonic polygonizations
- A hierarchy of simple polygons
- Walkable polygons
- Street polygons
- 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)

- Minkowski metrics
- Diameter algorithms for convex polygons
- Two-coins algorithm
- Multimodal functions
- Diameter via rotating calipers
- Antipodal pairs
- O(n) time for convex polygons
- Convex hull algorithms for points in the plane
- Rosenberg and Landgridge algorithm - O(n^3) time
- The Jarvis march (gift wrapping) - O(hn)
- The 3-coins algorithm for polygons - O(n)
- The Graham scan and star-shaped polygonizations
- Web: 7.1 - Mikowski metrics
- Web: 7.1.1 - Distance
- Web: 7.1.2 - Manhattan metric
- Text: Chapter 3- Convex hulls in the plane
- Web: 7.1.2 - Taxicab metric applet
- Web: 7.6.1 - Jaqueline Chen's tutorial on width and line fitting
- Web: 7.7 - Rotating calipers

- More on convex hulls
- Divide and conquer
- With presorting
- Without presorting and rotating-caliper merge
- Lower bound
- The throw-away principle
- Linear expected time algorithms
- Handout - Multimodality
- Handout - Snyder-Tang algorithm
- Web: 10.1 - Convex hull applet
- Web: 7.7.1 - Rotating caliper page of Hormoz Pirzadeh

- A hierarchy of simple polygons cont.
- L-convex polygons
- Weakly externally visible polygons
- Edge-visible polygons
- Convex hulls and triangulations of special polygons with the 3-coins algorithm
- Edge-visible polygons
- Weakly-externally visible polygons
- Computing the diameter of a polygon
- Computing the diameter of a set of points
- Triangulations, sorting and lower bounds
- Convex hulls of polygons
- O(n) time convex hulls of simple polygons
- The Graham-Yao algorithm
- Melkman's on-line algorithm
- Handout: the Graham-Yao algorithm
- Handout: Melkman's algorithm
- Web: 7.7.1 - Rotating caliper page of Hormoz Pirzadeh

**Movable separability of sets:**- Balls in space (Dawson's theorem)
- Orthogonal boxes (Guibas-Yao theorem)
- Convex olygons and polyhedra
- The width of a set (definition)
- Passing a chair through a door (Strang's theorem)
- O(n) algorithm for computing the width of a convex polygon
- Separating monotone polygons
- Star-shaped polygons and polyhedra
- 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 - Pierre Lang's tutorial on Melkman's algorithm
- 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 separating star-shaped bodies
- Separating two simple polygons
- Dual-tree of a triangulated polygon
- Shortest paths inside polygons
- Relative (geodesic) convex hulls

**Intersectig convex polygons:**- Slab method of Shamos & Hoey
- Via rotating caliper method and sail-polygons
- Divide & Conquer algorithm for intersecting half-planes
- Introduction to Voronoi diagrams
- Text: Chapter 8, Motion planning
- Text: 7.1 to 7.9 - Intersection problems
- Web: 13.1.3 - A simple linear algorithm for intersecting convex polygons
- 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(properties)
- Nearest neighbor graphs
- Minimum spanning trees
- Relative neighborhood graphs
- Gabriel graphs
- Delaunay triangulations
- NNG-MST-RNG-GG-DT relationships
- Computing proximity graphs
- Flipping algorithm for the Delaunay triangulation
- Proximity graphs via local search of the Delaunay triangulation
- Bucketing methods
- Computing proximity graphs (cont.)
- Voronoi diagram algorithms
- Via half-plane intersections
- Rhynsberger's algorithm - O(n^2)
- Divide and conquer - O(n log n)
- Furthest-point Voronoi diagrams
- The smallest enclosing circle
- Alpha hulls and shapes
- Translation ordering of rectangles
- Triangulating line segments (induction proof)
- Voronoi diagrams and Delaunay triangulations in 2D via convex hulls in 3D
- Arrangements of lines
- Facility location
- Text: 5 - Voronoi diagrams and applications
- 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

**Problem Assignment 4 "due"
November 16, 2000**

- Sphere of influence graph
- Convex hulls in 3 dimensions:
- Beneath-beyond method in O(n^2) time
- O(n log n) time (Preparata & Hong algorithm)
- Voronoi diagrams in 2D via convex hulls in 3D
- Computing nice viewpoints of objects in space
- Regular projections in knot theory
- Wirtinger projections in computer vision
- Visualization in computer graphics
- Handling degeneracies in computational geometry
- No two points on a vertical line (2 and 3 dimensions)
- Decision problem
- Computation problem
- Optimization problem
- Largest gap problem
- Gonzales' algorithm with floor functions and pigeonhole principle
- Web: 18.7 - Removing extrinsic degeneracies in computational geometry
- Web: 18.8 - Computing nice viewpoints of objects in space
- 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

**Course revision**

**Course Evaluations**