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
- Introduce course
- Models of computation
- The straight-edge-and-compass computer
- The tooth-pick computer
- Review projects
Problem Assignment 1 out -
"due" Sept. 21
- Constructing
a square with the Toothpick Computer
- Circles
enclosing polygons
- Recognizing
if a (possibly crossing) polygon is convex (and simple) in linear time
Lecture 2
- Review more projects
- The Real RAM (ceiling and floor functions)
- Define polygons (Jordan curve theorem)
- Data structures for polygons (standard form)
- Area of a triangle (of a polygon)
- Sidedness test, point inclusion in a triangle (in a convex polygon)
- Segment intersection test
Reading Assignment
- Text: 1.3 - Area of a polygon
- Web: 1.4 - Polygons and representations
- Web: 1.5 - Computing the area of a polygon
- Web: 1.6.1 - Notes on methods of proof
- Web: 1.6.2 - Notes on how to do proofs
- Web: 1.1.3 - A New Look at Euclid's Second Proposition (PostScript)
- Web: 2.1 - Jordan curve theorem
- Text: 1.5 - Segment intersection
Suggested Play
- Web: 1.1.1 - Applet of Francois Labelle
- Web: 2.1 - Octavian Cismasu's applet
Week 2-Sept 12
and 14
Lecture 3
- Discuss projects
- Chvatal's art gallery theorem
- Fisk's proof
- Point inclusion continued
- Queries in O(log n) time
Lecture 4
- Discuss projects
- Point inclusion continued
- In a simple polygon
- The plumb-line algorithm
- Query mode for simple polygons
- Smallest enclosing circle
- Brute force algorithm
- Testing convexity
- Of simple polygons
Reading Assignment
- Text: Chapter 1
- Web: 3.1-3.3 - Testing the orientation and convexity
of a polygon
- Web: 4.2.1 - Ian Garton's tutorial on polygon
triangulation
Suggested Play
- Web: 4.2.1 - Ian Garton's applets
Week 3-Sept 19
and 21
Lecture 5
- Two-ears theorem
- Via induction
- Via dual trees
- Triangulating simple polygons
- Via ear-cutting
- Via diagonal insertion
- Convex partitioning of simple polygons
Lecture 6
- Polygonizations of point sets
- Maximal vectors
- Monotonic polygonizations
- A hierarchy of simple polygons
- Walkable polygons
- Street polygons
Problem Assignment 2 "due"
October 10, 2000
- Enclosing
a convex polygon with a triangle
- Midpoint
polygonization of points
- Visibility
in street-polygons and walkable-polygons
Reading Assignment
- Text: Chapter 2 - Polygon partitioning
- Web: 5.1.2 - Tutorial on art gallery theorem
- Web: 6.1 - Polygonization tutorial
Suggested Play
- Web: 5.1.2 - Thierry Dagnino's applet
- Web: 6.1 - Polygonization applet
- Web: 6.2 - Polygonization counter (applet)
Week 4-Sept 26
and 28
Lecture 7
- Minkowski metrics
- Diameter algorithms for convex polygons
- Two-coins algorithm
- Multimodal functions
Lecture 8
- Diameter via rotating calipers
- Antipodal pairs
- O(n) time for convex polygons
- Convex hull algorithms for points in the plane
- Rosenberg and Landgridge algorithm - O(n^3) time
- The Jarvis march (gift wrapping) - O(hn)
- The 3-coins algorithm for polygons - O(n)
- The Graham scan and star-shaped polygonizations
Reading Assignment
- Web: 7.1 - Mikowski metrics
- Web: 7.1.1 - Distance
- Web: 7.1.2 - Manhattan metric
- Text: Chapter 3- Convex hulls in the plane
Suggested Play
- Web: 7.1.2 - Taxicab metric applet
- Web: 7.6.1 - Jaqueline Chen's tutorial on width
and line fitting
- Web: 7.7 - Rotating calipers
Week 5 - Oct 3
and 5
Lecture 9 First
In-Class Exam
Lecture 10
- More on convex hulls
- Divide and conquer
- With presorting
- Without presorting and rotating-caliper merge
- Lower bound
- The throw-away principle
- Linear expected time algorithms
Reading Assignment
- Handout - Multimodality
- Handout - Snyder-Tang algorithm
Suggested Play
- Web: 10.1 - Convex hull applet
- Web: 7.7.1 - Rotating caliper page of Hormoz
Pirzadeh
Week 6 - Oct
10 and 12
Lecture 11
- A hierarchy of simple polygons cont.
- L-convex polygons
- Weakly externally visible polygons
- Edge-visible polygons
- Convex hulls and triangulations of special polygons
with the 3-coins algorithm
- Edge-visible polygons
- Weakly-externally visible polygons
Problem Assignment 3 "due"
October 31, 2000
- Computing
the diameter of a polygon
- Computing
the diameter of a set of points
- Triangulations,
sorting and lower bounds
- Convex
hulls of polygons
Lecture 12
- O(n) time convex hulls of simple polygons
- The Graham-Yao algorithm
- Melkman's on-line algorithm
Reading Assignment
- Handout: the Graham-Yao algorithm
- Handout: Melkman's algorithm
Suggested Play
- Web: 7.7.1 - Rotating caliper page of Hormoz
Pirzadeh
Week 7-Oct 17 and
19
Lecture 13
- Movable separability of sets:
- Balls in space (Dawson's theorem)
- Orthogonal boxes (Guibas-Yao theorem)
- Convex olygons and polyhedra
- The width of a set (definition)
Lecture 14
- Passing a chair through a door (Strang's theorem)
- O(n) algorithm for computing the width of a convex polygon
- Separating monotone polygons
- Star-shaped polygons and polyhedra
Reading Assignment
- Text: 8.7 - movable separability of objects
- Web: 17.1 - The match-stick game
- Web: 17.2.1 - Separating objects in space
- Web: 17.2 - Movable separability of objects
- Web: 10.3.1 - Pierre Lang's tutorial on Melkman's
algorithm
Suggested Play
- Web: 10.3.1 - Melkman's algorithm applet
- Web: 17.1 - Applet for the match-stick game
- Web: 17.2.1 - Applet for separating star-shaped
polygons
Week 8-Oct 24 and
26
Lecture 15
- Dawson's theorem on separating star-shaped bodies
- Separating two simple polygons
- Dual-tree of a triangulated polygon
- Shortest paths inside polygons
- Relative (geodesic) convex hulls
Lecture 16
- Intersectig convex polygons:
- Slab method of Shamos & Hoey
- Via rotating caliper method and sail-polygons
- Divide & Conquer algorithm for intersecting
half-planes
- Introduction to Voronoi diagrams
Reading Assignment
- Text: Chapter 8, Motion planning
- Text: 7.1 to 7.9 - Intersection problems
- Web: 13.1.3 - A simple linear algorithm for intersecting
convex polygons
- Web: 13.1.2 - Eric Plante's tutorial on convex
polygon intersection
- Web: 17.4 - Separating two simple polygons by
a single translation
Suggested Play
- Web: 17.5.3 - Shortest path applet
- Web: 13.1.2 - Applet for convex polygon intersection
Week 9-Oct 31 and
Nov 2
Lecture 17
- Proximity graphs(properties)
- Nearest neighbor graphs
- Minimum spanning trees
- Relative neighborhood graphs
- Gabriel graphs
- Delaunay triangulations
- NNG-MST-RNG-GG-DT relationships
- Computing proximity graphs
- Flipping algorithm for the Delaunay triangulation
- Proximity graphs via local search of the Delaunay
triangulation
- Bucketing methods
Lecture 18
- Computing proximity graphs (cont.)
- Voronoi diagram algorithms
- Via half-plane intersections
- Rhynsberger's algorithm - O(n^2)
- Divide and conquer - O(n log n)
- Furthest-point Voronoi diagrams
- The smallest enclosing circle
- Alpha hulls and shapes
Problem Assignment 4 "due"
November 16, 2000
- Translation
ordering of rectangles
- Triangulating
line segments (induction proof)
- Voronoi
diagrams and Delaunay triangulations in 2D via convex hulls in 3D
- Arrangements
of lines
- Facility
location
Reading Assignment
- Text: 5 - Voronoi diagrams and applications
- Web: 14.3 - The relative neighborhood graph
Suggested Play
- Web: 14.1 - Minimal spanning tree applet
- Web: 14.6.1 - Fantastic applet for Voronoi diagrams
and Delaunay triangulations
Week 10-Nov 7
and 9
Lecture 19
- Sphere of influence graph
- Convex hulls in 3 dimensions:
- Beneath-beyond method in O(n^2) time
- O(n log n) time (Preparata & Hong algorithm)
- Voronoi diagrams in 2D via convex hulls in 3D
Lecture 20
- Computing nice viewpoints of objects in space
- Regular projections in knot theory
- Wirtinger projections in computer vision
- Visualization in computer graphics
- Handling degeneracies in computational geometry
- No two points on a vertical line (2 and 3 dimensions)
- Decision problem
- Computation problem
- Optimization problem
- Largest gap problem
- Gonzales' algorithm with floor functions and pigeonhole principle
Reading Assignment
- Web: 18.7 - Removing extrinsic degeneracies in
computational geometry
- Web: 18.8 - Computing nice viewpoints of objects
in space
- Web: 14.9 - Proximity graphs (including a survey
paper)
- Text: Chapter 4 - Convex hulls in 3 dimensions
- Web: 14.3 - Relative neighborhood graph
- Web: 14.8 - Sphere-of-influence graph tutorial
(Richard Unger)
Suggested Play
- Web: 14.8 - Sphere-of-influence graph applet
Week 11-Nov 14 and 16
Lecture 21: Guest
Lecturer: Michael Soss
- 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
- Course Evaluations
Lecture 26:
Student Presentations
Week 14 - Dec 5
Lecture 26: No
class due to Study Day