Lecture Descriptions, Exams, Homework, and Play

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

Week 1-Sept 5 and 7

Lecture 1
1. Introduce course
2. Models of computation
1. The straight-edge-and-compass computer
2. The tooth-pick computer
3. Review projects
Lecture 2
1. Review more projects
2. The Real RAM (ceiling and floor functions)
3. Define polygons (Jordan curve theorem)
4. Data structures for polygons (standard form)
5. Area of a triangle (of a polygon)
6. Sidedness test, point inclusion in a triangle (in a convex polygon)
7. Segment intersection test
1. Text: 1.3 - Area of a polygon
2. Web: 1.4 - Polygons and representations
3. Web: 1.5 - Computing the area of a polygon
4. Web: 1.6.1 - Notes on methods of proof
5. Web: 1.6.2 - Notes on how to do proofs
6. Web: 1.1.3 - A New Look at Euclid's Second Proposition (PostScript)
7. Web: 2.1 - Jordan curve theorem
8. Text: 1.5 - Segment intersection
Suggested Play
1. Web: 1.1.1 - Applet of Francois Labelle
2. Web: 2.1 - Octavian Cismasu's applet

Week 2-Sept 12 and 14

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

Week 3-Sept 19 and 21

Lecture 5
1. Two-ears theorem
1. Via induction
2. Via dual trees
2. Triangulating simple polygons
1. Via ear-cutting
2. Via diagonal insertion
3. Convex partitioning of simple polygons
Lecture 6
1. Polygonizations of point sets
1. Maximal vectors
2. Monotonic polygonizations
2. A hierarchy of simple polygons
1. Walkable polygons
2. Street polygons
Problem Assignment 2 "due" October 10, 2000
1. Text: Chapter 2 - Polygon partitioning
2. Web: 5.1.2 - Tutorial on art gallery theorem
3. Web: 6.1 - Polygonization tutorial
Suggested Play
1. Web: 5.1.2 - Thierry Dagnino's applet
2. Web: 6.1 - Polygonization applet
3. Web: 6.2 - Polygonization counter (applet)

Week 4-Sept 26 and 28

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

Week 5 - Oct 3 and 5

Lecture 9 First In-Class Exam
Lecture 10
1. More on convex hulls
1. Divide and conquer
1. With presorting
2. Without presorting and rotating-caliper merge
2. Lower bound
3. The throw-away principle
4. Linear expected time algorithms
1. Handout - Multimodality
2. Handout - Snyder-Tang algorithm
Suggested Play
1. Web: 10.1 - Convex hull applet
2. Web: 7.7.1 - Rotating caliper page of Hormoz Pirzadeh

Week 6 - Oct 10 and 12

Lecture 11
1. A hierarchy of simple polygons cont.
1. L-convex polygons
2. Weakly externally visible polygons
3. Edge-visible polygons
2. Convex hulls and triangulations of special polygons with the 3-coins algorithm
1. Edge-visible polygons
2. Weakly-externally visible polygons
Lecture 12
1. O(n) time convex hulls of simple polygons
1. The Graham-Yao algorithm
2. Melkman's on-line algorithm
1. Handout: the Graham-Yao algorithm
2. Handout: Melkman's algorithm
Suggested Play
1. Web: 7.7.1 - Rotating caliper page of Hormoz Pirzadeh

Week 7-Oct 17 and 19

Lecture 13
1. Movable separability of sets:
1. Balls in space (Dawson's theorem)
2. Orthogonal boxes (Guibas-Yao theorem)
3. Convex olygons and polyhedra
4. The width of a set (definition)
Lecture 14
1. Passing a chair through a door (Strang's theorem)
2. O(n) algorithm for computing the width of a convex polygon
3. Separating monotone polygons
4. Star-shaped polygons and polyhedra
1. Text: 8.7 - movable separability of objects
2. Web: 17.1 - The match-stick game
3. Web: 17.2.1 - Separating objects in space
4. Web: 17.2 - Movable separability of objects
5. Web: 10.3.1 - Pierre Lang's tutorial on Melkman's algorithm
Suggested Play
1. Web: 10.3.1 - Melkman's algorithm applet
2. Web: 17.1 - Applet for the match-stick game
3. Web: 17.2.1 - Applet for separating star-shaped polygons

Week 8-Oct 24 and 26

Lecture 15
1. Dawson's theorem on separating star-shaped bodies
2. Separating two simple polygons
3. Dual-tree of a triangulated polygon
4. Shortest paths inside polygons
5. Relative (geodesic) convex hulls
Lecture 16
1. Intersectig convex polygons:
1. Slab method of Shamos & Hoey
2. Via rotating caliper method and sail-polygons
2. Divide & Conquer algorithm for intersecting half-planes
3. Introduction to Voronoi diagrams
1. Text: Chapter 8, Motion planning
2. Text: 7.1 to 7.9 - Intersection problems
3. Web: 13.1.3 - A simple linear algorithm for intersecting convex polygons
4. Web: 13.1.2 - Eric Plante's tutorial on convex polygon intersection
5. Web: 17.4 - Separating two simple polygons by a single translation
Suggested Play
1. Web: 17.5.3 - Shortest path applet
2. Web: 13.1.2 - Applet for convex polygon intersection

Week 9-Oct 31 and Nov 2

Lecture 17
1. Proximity graphs(properties)
1. Nearest neighbor graphs
2. Minimum spanning trees
3. Relative neighborhood graphs
4. Gabriel graphs
5. Delaunay triangulations
6. NNG-MST-RNG-GG-DT relationships
2. Computing proximity graphs
1. Flipping algorithm for the Delaunay triangulation
2. Proximity graphs via local search of the Delaunay triangulation
3. Bucketing methods
Lecture 18
1. Computing proximity graphs (cont.)
1. Voronoi diagram algorithms
1. Via half-plane intersections
2. Rhynsberger's algorithm - O(n^2)
3. Divide and conquer - O(n log n)
2. Furthest-point Voronoi diagrams
1. The smallest enclosing circle
3. Alpha hulls and shapes

Problem Assignment 4 "due" November 16, 2000

1. Text: 5 - Voronoi diagrams and applications
2. Web: 14.3 - The relative neighborhood graph
Suggested Play
1. Web: 14.1 - Minimal spanning tree applet
2. Web: 14.6.1 - Fantastic applet for Voronoi diagrams and Delaunay triangulations

Week 10-Nov 7 and 9

Lecture 19
1. Sphere of influence graph
2. Convex hulls in 3 dimensions:
1. Beneath-beyond method in O(n^2) time
2. O(n log n) time (Preparata & Hong algorithm)
3. Voronoi diagrams in 2D via convex hulls in 3D
Lecture 20
1. Computing nice viewpoints of objects in space
1. Regular projections in knot theory
2. Wirtinger projections in computer vision
3. Visualization in computer graphics
2. Handling degeneracies in computational geometry
1. No two points on a vertical line (2 and 3 dimensions)
2. Decision problem
3. Computation problem
4. Optimization problem
1. Largest gap problem
2. Gonzales' algorithm with floor functions and pigeonhole principle
1. Web: 18.7 - Removing extrinsic degeneracies in computational geometry
2. Web: 18.8 - Computing nice viewpoints of objects in space
3. Web: 14.9 - Proximity graphs (including a survey paper)
4. Text: Chapter 4 - Convex hulls in 3 dimensions
5. Web: 14.3 - Relative neighborhood graph
6. Web: 14.8 - Sphere-of-influence graph tutorial (Richard Unger)
Suggested Play
1. Web: 14.8 - Sphere-of-influence graph applet

Week 11-Nov 14 and 16

Lecture 21: Guest Lecturer: Michael Soss
1. Course revision

Week 13-Nov 28 and 30

Lecture 25: Student Presentations
1. Course Evaluations

Week 14 - Dec 5

Lecture 26: No class due to Study Day