CS-507A Computational Geometry

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

Problem Assignment 1 out - "due" Sept. 21

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

Reading Assignment

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

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

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

Reading Assignment

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

Reading Assignment

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

Problem Assignment 3 "due" October 31, 2000

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 12

1. O(n) time convex hulls of simple polygons
1. The Graham-Yao algorithm
2. Melkman's on-line algorithm

Reading Assignment

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

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

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

Reading Assignment

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

Reading Assignment

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

Lecture 22: Second Midterm Exam

Week 12-Nov 21 and 23

Lecture 23: Student Presentations

Lecture 24: Student Presentations

Week 13-Nov 28 and 30

Lecture 25: Student Presentations

1. Course Evaluations

Lecture 26: Student Presentations

Week 14 - Dec 5