# 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 Peterson

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

### Week 1-Sept 2

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

### Week 2-Sept 7 and 9

##### Lecture #2:
1. The power of the collapsing compass
2. Case analysis in proofs
3. The Real RAM (ceiling and floor functions)
4. Define polygons (Jordan curve theorem)
5. Data structures for polygons (standard form)
6. Area of a triangle (polygon)
7. Sidedness test, point inclusion in a triangle
##### Lecture #3:
1. Discuss some projects
2. Line segment intersection
3. Point inclusion
1. In a convex polygon
1. Query mode in a convex polygon
1. Text: 1.3 - Area of a polygon
2. Web: 1.1.3 - A New Look at Euclid's Second Proposition (PostScript)
3. Web: 2.1 - Jordan curve theorem
4. 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 3-Sept 14 and 16

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

### Week 4-Sept 21 and 23

##### Lecture #6:
1. Chvatal's art gallery theorem
1. Three-coloring triangulated polygons
2. The pigeonhole principle
3. Star-shaped polygons and fans
2. Edge guards
3. Two-ears theorem
1. Via induction
2. Via dual trees
4. Triangulating simple polygons in quadratic time
5. Convex partitioning of simple polygons
##### Lecture #7:
1. Polygonizations of point sets
1. Monotonic polygonizations
2. Star-shaped polygonizations
3. Spiral polygonizations
##### Problem Assignment #1 due(#2 out)
1. Enclosing a convex polygon with a triangle
2. Midpoint polygonization of points
3. Visibility in street-polygons and walkable-polygons
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 5-Sept 28 and 30

##### Lecture #8:
1. Diameter of a convex polygon
2. Two-coins algorithm
3. Multimodality of distance functions
##### Lecture #9:
1. Antipodal pairs
2. Rotating calipers solution to diameter problem
3. The width of a set
4. Passing a chair through a door
5. Smallest enclosing rectangle
6. Maximum distance between two convex polygons
1. Handout - Multimodality
2. Handout - Distance
3. Handout - Snyder-Tang algorithm
4. Web: 7.1 - Mikowski metrics
5. Web: 7.1.1 - Distance
6. Web: 7.1.2 - Manhattan metric
Suggested Play
1. Web: 7.1.2 - Taxicab metric applet
2. Web: 7.5.1 - Jaqueline Chen's tutorial on width and line fitting
3. Web: 7.6.1 - Rotating caliper page of Hormoz Pirzadeh

### Week 6-Oct 5 and 7

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

### Week 7-Oct 12 and 14

##### Lecture #12:
1. O(n) time convex hulls of simple polygons
1. Melkman's on-line algorithm
2. Visibility in polygons
1. Edge-visible polygons (weak, strong and complete visibility)
2. O(n) algorithm for testing edge visibility (3-coins application)
##### Problem Assignment #3 out (#2 due)
1. Computing the diameter of a polygon
2. Computing the diameter of a set of points
3. Triangulations, sorting and lower bounds
4. Convex hulls of polygons
##### Lecture #13:
1. Movable separability of sets:
1. Balls in space (Dawson's theorem)
2. Orthogonal boxes (Guibas-Yao theorem)
3. Convex polyhedra
4. Star-shaped polygons
1. Handout: Melkman's algorithm
2. Handout: Edge visibility
3. Web: 10.3.1 - Pierre Lang's tutorial on Melkman's algorithm
4. Web: 11.2 - Edge visibility
5. Text: 8.7 - movable separability of objects
6. Web: 17.1 - The match-stick game
7. Web: 17.2.1 - Separating objects in space
8. Web: 17.2 - Movable separability of objects
##### 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 19 and 21

##### Lecture #14:
1. Dawson's theorem on star-shaped bodies
2. Dual-tree of a triangulated polygon
3. Shortest paths inside polygons
4. Relative (geodesic) convex hulls
Lecture #15: HTML Project due October 21st
1. Separating 2 simple polygons (finish proof)
2. Proof of correctness of 3-coins algorithm
1. For triangulating edge-visible polygons
2. For convex hull of weakly externally visible polygons
3. Applications of 3-coins algorithm
1. Triangulating monotonic polygons
2. Divide & Conquer algorithm for intersecting half-planes (convex polygons)
3. Divide & Conquer algorithm for triangulating sets of points
1. Text: Chapter 8, Motion planning
2. Text: 7.6 - Intersection of convex polygons
3. Web: 13.1.3 - A simple linear algorithm for intersecting convex polygons (same as handout)
4. Handout: Sack & Toussaint paper on separability
5. Web: 13.1.2 - Eric Plante's tutorial on convex polygon intersection
6. 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 26 and 28

##### Lecture #16:
1. Proximity graphs
1. Nearest neighbor graphs
2. Minimal spanning trees
3. Relative neighborhood graphs
4. Gabriel graphs
5. Delaunay triangulations
2. Computing proximity graphs
1. Voronoi diagram algorithms
1. Via half-plane intersections
2. Rhynsberger's algorithm - O(n^2)
##### Lecture #17: Class Test (75 minutes, closed book)
1. Text: 5.1 to 5.4 - Voronoi diagrams
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 2 and 4

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

### Week 11-Nov 9 and 11

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

### Week 12-Nov 16 and 18

##### Lecture #22: Problem Assignment #4 due, #5 out
1. Triangulations revisited:
1. Finding an ear in linear time with prune-and-search
2. Efficient practical polygon triangulation
1. Modified Graham scan
2. Sleeve-searching algorithm
3. Updating triangulations
1. Inserting and deleting vertices
2. Inserting and deleting edges

Problem Assignment #5

1. Arrangements of lines
2. Facility location
##### Lecture #23:
1. Removing degeneracies in computational geometry
1. Intrinsic and algorithm-induced degeneracies
2. No two points on a vertical line in 2 and 3 dimensions
3. Decision, computation and optimization problem
4. Lower bound via element-uniqueness
1. Web: 4.1 - History of polygon triangulation
2. Web: 4.4 - Finding an ear with prune-and-search
3. Web: 4.5 - Modified Graham scan
4. Web: 12 - Tutorial on updating triangulations of points and line segments
5. Handout: Output-complexity sensitive polygon triangulation
6. Web: 18.1-4 and 18.7 - Removing degeneracies
##### Suggested Play
1. Web: 4.4 - Modified Graham scan applet of Ian Garton
2. Web: 12 - Updating triangulations applets

### Week 13-Nov 23 and 25

##### Lecture #24:
1. Degeneracies cont.
1. Smallest spherical cap containing n points
2. No two points with the same x, y or z coordinates.
2. Linear programming in linear time (Meggido's algorithm)
1. Linear median finding algorithm of Blum, Floyd, Pratt, Rivest & Tarjan
##### Lecture #25: Course Evaluations
1. Smallest enclosing circle in linear time (Meggido's algorithm)
2. Smallest spherical cap containing a set of points
1. On a sphere
2. On a hemisphere