CS-507A Computational Geometry

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

Reading Assignment

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

Problem Assignment #1 out - due Sept. 23

1. Constructing a square with the Toothpick Computer
2. Circles enclosing polygons
3. Recognizing if a (possibly crossing) polygon is convex (and simple) in linear time

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

Reading Assignment

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

Reading Assignment

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

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

Reading Assignment

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

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

Reading Assignment

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

Reading Assignment

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

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

Reading Assignment

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)

Reading Assignment

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

Reading Assignment

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

Reading Assignment

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

Reading Assignment

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

Reading Assignment

1. Web: Chapter 16 - Facility location

Suggested Play

1. Web: Chapter 16 applets

Week 14-Nov 30 and Dec 2

Lecture #26: Review course

Lecture #27: Class Test (75 minutes, closed book)

1. Problem Assignment #5 due
2. Entire Web Project including Java Applet due December 9th.