COMP-507A Computational Geometry - Fall 2006

Lecture Descriptions, Homework, and Play

"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

Problem Assignment 1 out - "due" September 19

1. Constructing a square with the Toothpick Computer
2. Measuring distances with rulers that have few marks
3. Circles enclosing polygons
4. Recognizing if a (possibly crossing) polygon is convex (and simple) in linear time

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

Reading Assignment

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

Reading Assignment

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
2. 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. Enclosing a convex polygon with a triangle
2. Midpoint polygonization of points
3. Visibility in street-polygons and walkable-polygons

Reading Assignment

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

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)

Reading Assignment

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

Reading Assignment

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 11: First In-Class Exam - Examples ( 2000 2003)

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. 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

Reading Assignment

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

Reading Assignment

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

Suggested Play: none this week

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. Translation ordering of rectangles
2. Triangulating line segments (induction proof)
3. Voronoi diagrams and Delaunay triangulations in 2D via convex hulls in 3D
4. Arrangements of lines
5. Facility location

Reading Assignment

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

Reading Assignment

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

Reading Assignment

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 11 - Nov 14 and 16

Lecture 21: Second Midterm Exam (Examples of previous exams:)

• 2003
• 2001
• 2000
• 1999

Lecture 22: Student Presentations

Week 12 - Nov 21 and 23

Lecture 23: Student Presentations

Lecture 24: Student Presentations and Course Evaluations

Week 13 - Nov 28 and 30

Lecture 25: Student Presentations

Week 14 - Dec 5

Lecture 25: Student Presentations