# Lecture Descriptions, 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 Pedersen Week:  1 - 2 - 3 -4 - 5 - 6 - 7 - 8 - 9 - 10 - 11 - 12 - 13 ### Week 1 - Sept 5 and 7

##### Lecture 1
1. Introduce course
2. Smallest enclosing circle
1. Brute force algorithm
3. Models of computation
1. The straight-edge-and-compass computer
2. The tooth-pick computer
3. Rulers with few marks
4. 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. Point inclusion:
1. In a triangle
2. In a simple polygon
3. The plumb-line algorithm
7. Sidedness test
8. Segment intersection test
1. Text: 1.3 - Area of a polygon
2. Text: 1.5 - Segment intersection
3. Web: 1.6.1 - Notes on methods of proof
4. Web: 1.1.3 - A New Look at Euclid's Second Proposition (PostScript)
5. Web: 2.1 - Jordan curve theorem
##### Suggested Play
1. Web: 1.1.1 - Applet of Francois Labelle

### Week 2 - Sept 12 and 14

##### Lecture 3
1. Discuss projects
2. Point inclusion continued
1. Query mode for simple polygons
3. Testing convexity
1. Of simple polygons
2. Of crossing polygons
##### Lecture 4
1. Two-ears theorem
1. Via induction
2. Via dual trees
2. Chvatal's art gallery theorem
1. Fisk's proof
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. Triangulating simple polygons
1. Via ear-cutting
2. Via diagonal insertion
2. Convex partitioning of simple polygons
3. A hierarchy of simple polygons
1. Walkable polygons
2. Street polygons
##### Lecture 6:
1. Polygonizations of point sets
1. Maximal vectors
2. Monotonic polygonizations
3. Star-shaped polygonizations
4. Onion polygonizations
##### Problem Assignment 2: "due" October 10
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 Sept 28

Lecture 7
1. Diameter algorithms for convex polygons
1. Snyder-Tang algorithm
2. Two-coins algorithm
2. Multimodal functions
##### Lecture 8
1. Diameter via rotating calipers
1. Antipodal pairs
2. O(n) time for convex polygons
1. 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)
1. Web: 7.1 - Mikowski metrics
2. Web: 7.1.1 - Distance
3. Web: 7.1.2 - Manhattan metric
4. Web: 7.5.1 - Diameter algorithms
5. Handout - Multimodality
6. Handout - Snyder-Tang algorithm
##### 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:
1. The Graham scan and star-shaped polygonizations
2. The 3-coins algorithm for polygons - O(n)
1. Star-shaped polygons
2. Monotone polygons
3. Weakly externally visible polygons
3. Lower bound by reduction from sorting
##### Lecture 10:
1. Triangulation of point sets via sorting and 3-coins algorithm
2. More convex hulls:
1. The Throw-Away Principle and O(n) expected time algorithms
2. Quickhull
1. Quickhull with medians
3. Sequential insertion (beneath-beyond)
1. With presorting in O(n log n) time
2. Without presorting and  point inclusion testing in O(n log n) time
1. Text: Chapter 3 - Convex hulls in the plane
2. Web: 10.3.3 - A fast convex hull algorithm (algorithm of Akl and Toussaint)
##### 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
1. Movable separability of sets:
1. Sofa problems
2. Balls in space (Dawson's theorem)
3. Orthogonal boxes (Guibas-Yao theorem)
4. Convex polygons in 2 dimensions
##### Problem Assignment 3: "due" October 24
1. Text: Chapter 4
2. Web: 7.5.1 - Diameter algorithms
3. Web: 10.4.1 - 3-coins algorithm
4. Handout: the Graham-Yao algorithm
5. Handout: Melkman's algorithm
##### Suggested Play
1. Web: 17.2 - Movable separability of objects
2. Web: 17.1 - Applet for the match-stick game
3. Web: 17.2.1 - Applet for separating star-shaped polygons
4. Web: 7.7.1 - Rotating caliper page of Hormoz Pirzadeh
5. Web: 7.5.1 - Diameter algorithm applet
6. Web: 10.4.1 - 3-coins algorithm applet

### Week 7-Oct 17 and 19

##### Lecture 13:
1. Convex hulls continued:
1. Randomized sequential insertion
2. Divide and conquer:
1. With presorting
2. Without presorting and rotating-caliper merge
3. Sequential insertion (beneath-beyond)
1. In 3-dimensions in O(n^2) time
##### Lecture 14:
1. Convex hulls continued:
1. Output-sensitive convex hull algorithms:
1. Kirkpatrick-Seidel's ultimate algorithm
2. Timothy Chan's algorithm
2. Convex hulls of simple polygons:
1. O(n) time convex hulls of simple polygons
1. The Graham-Yao algorithm
2. Melkman's on-line algorithm
1. Web: 10.1.1.1.1 - Randomized incremental convex hull algorithm
2. Web: 10.1.1.7 - Kirkpatrick-Seidel ultimate algorithm
3. Web: 10.1.6 - Timothy Chan's algorithm

### Week 8 - Oct 24 and 26

##### Lecture 15
1. Movable separability problems:
1. Convex polyhedra 3 dimensions
2. The width of a set (definition)
3. Passing a chair through a door (Strang's theorem)
4. O(n) algorithm for computing the width of a convex polygon
5. Separating star-shaped polygons and polyhedra
6. Dawson's theorem
##### Lecture 16
1. Movable separability problems:
1. Separating monotone polygons
2. Separating two simple polygons
3. Dual-tree of a triangulated polygon
4. Shortest paths inside polygons
5. Relative (geodesic) convex hulls

Problem Assignment 4 "due" November 14

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. Text: Chapter 8, Motion planning
5. Text: 7.1 to 7.9 - Intersection problems
6. Web: 13.1.3 - A simple linear algorithm for intersecting convex polygons
7. Web: 13.1.2 - Eric Plante's tutorial on convex polygon intersection
8. 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. Intersectig convex polygons:
1. Slab method of Shamos & Hoey
2. Via rotating caliper method and sail-polygons
3. Divide & Conquer algorithm for intersecting half-planes
##### Lecture 18
1. Introduction to Voronoi diagrams
2. 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
3. Computing proximity graphs
1. Proximity graphs via local search of the Delaunay triangulation
2. Relative neighborhood graph algorithms and counter examples
3. Bucketing methods
1. Text: 5 - Voronoi diagrams and applications
2. Web: 14.3 - The relative neighborhood graph
3. Web: 14.9 - Proximity graphs (including a survey paper)
##### 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. Alpha-hulls and alpha-shapes
2. Sphere-of-influence graph
3. Nearest and furthest-point Voronoi diagrams
1. Flipping algorithm for the Delaunay triangulation
2. Voronoi diagram algorithms
1. Via half-plane intersections in O(n^2 log n) time
4. Proof that the nearest neighbor is a Voronoi neighbor
5. Voronoi diagram algorithms - cont.
1. Rhynsberger's algorithm - O(n^2)
2. Voronoi diagrams in 2D via convex hulls in 3D by lifting points to paraboloid
3. Voronoi diagram algorithm via divide and conquer - O(n log n)
6. Properties of furthest-point Voronoi diagrams
1. The smallest enclosing circle in O(n log n) time via  furthest-point Voronoi diagrams
##### Lecture 20
1. Linear programming in linear time in the plane (Meggido's algorithm)
2. Efficient polygon triangulation.
1. Sleeve searching algorithm in O(n(1+t)) time where t is the number of vertices of degree 3 in the dual tree of the triangulation delivered.
##### Handling degeneracies
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. Handout: Meggido's algorithm
2. Handout: Sleeve searching polygon triangulation algorithm
3. Web: 18.7 - Removing extrinsic degeneracies in computational geometry
4. Web: 18.8 - Computing nice viewpoints of objects in space
5. Web: 14.9 - Proximity graphs (including a survey paper)
6. Text: Chapter 4 - Convex hulls in 3 dimensions
7. Web: 14.3 - Relative neighborhood graph
8. Web: 14.8 - Sphere-of-influence graph tutorial (Richard Unger)
##### Suggested Play
1. Web: 14.8 - Sphere-of-influence graph applet

### Week 14 - Dec 5

Lecture 25: Student Presentations 