CS507A: Computational Geometry Lectures

If you find any links on the web that you think might be useful to other students, send them to me and I'll include them on this page.

Lecture 1: 5/9/2

• Course description.
• What is Computational Geometry?
• Models of computation:
  • RAM model
  • Real-RAM model
  • Ruler&Compass-RAM model
• The Cross Product and applications.
• Convexity: definition.
• Convex Hull CH(S) of a finite set S of points.
• Read:
  • Web: Classical Geometry.
  • Web: Convexity.

Lecture 2: 9/9/2

• Convexity
• properties of CH(S)+ algos :
  • definition of a vertex of CH(S).
  • A pt is a vertex iff it is not inside any triangle => O(n^4) algo.
  • properties of an edge => O(n^3) algo.
  • Jarvis march.
  • Graham scan original
  • Monotone Graham scan (linesweep, triangulation)
  • Incremental
• Read:
  • Point Inclusion problems
  • Polygonization of point sets
  • Convex Hulls
  • Textbook: Chapter I

Lecture 3: 12/9/2

• Course projects.
• MergeHull, merging two convex polygons.
• Lower bounds:
  • Adversary arguments.
  • Reductions.
  • Algebraic decision trees, Dobkin-Lipton's theorem
  • Read: Michiel Smid's lecture notes on lower bounds.

Lecture 4: 17/9/2 (covered by Greg Aloupis)

• Output sensitive convex hull algorithms:
  • Jarvis March
  • Quickhull
  • Kirkpatrick-Seidel Ultimate CH algorithm (.ps)
  • Chan's algorithm (.ps.gz) (read section 2)
• Convex hull of a simple polygon: Melkman's algorithm, and Sklansky's 3-coins algorithm.

Lecture 5: 19/9/2 (covered by Greg Aloupis)

• Two ears theorem, method for finding two ears.
• Proof that triangulation is always possible (ear-cutting and gluing back).
• Triangulate by finding diagonal.
• dual tree of a triangulation and 2 leaves = ears.
• Algorithms:
  • O(n^3) triangulation, brute force.
  • O(n^2) triangulation by finding ear in O(n), which needed:
  • finding ear in O(n) by GSP method.
• Art gallery, n/3 guards by coloring.
• Decomposing a monotone polygon into monotone mountains.
• introduction of Weakly Externally Visible (WEV). You can use 3coins to find the CH of a WEV polygon.
• See also notes and links on Greg's webpage.

Lecture 6: 24/9/2

• Further motivation for triangulations.
• Triangulation of the exterior of a WEV polygon using the 3 coins algorithm, in O(n) time.
• Weakly Internally Visible (WIV) polygons (visible from one of its edges. O(n) 3 coins algorithm for triangulating those.
• Monotone polygons, O(n) time decomposition into WIV polygons.
• Linesweep to decompose a polygon into monotone pieces.
• Read: Textbook chapter 3

Lecture 7: 26/9/2

• Triangulation in O(nR) where R = # of reflex vertices, using modified 3 coins.
• More on linesweep:
• Line segment intersection by linesweep.
• Degeneracies for line segment intersection.
• O(n) space for line segment intersection.
• Omega(n log(n)) lower bound for detecting a line segment intersection, in the algebraic decision tree model.
• Planar graphs: Euler's formula
• Read:
  • Textbook chapter 2
  • Seventeen proofs of Euler's formula.

Lecture 8: 1/10/2

• Data structures for planar graphs, Doubly Connected Edge List (DCEL), augmenting for fast walking. Space analysis.
• Point location data structures:
  • By Triangle testing - O(n) query time and space.
  • Ray shooting
  • O(log(n)) query time and O(n) space for star-shaped polygons
  • Dobkin-Lipton (slabs) - O(n^2) space and O(log(n)) query time
  • Kirkpatrick's: Simplifying triangulations (analysis next time).

Lecture 9: 3/10/2

• Kirkpatrick's point location data structure:
  • Construction by repeatedly removing independent vertices of low degree, pointer structure.
  • Performing searches.
  • Proof that there exist at least n/24 vertices of degree <12.
  • Query time, depth of the search structure.
  • Space.
• Trapezoidal decompositions, search structure and incremental construction algorithm.

Lecture 10: 8/10/2

• Randomized incremental trapezoidal decomposition algorithm, review and analysis.
• Read: Book chapter 6.

Lecture 11: 10/10/2

• Triangulations of sets of points
• Delaunay triangulations:
  • Maximizing the smallest angle
  • Empty circle property
  • Incremental construction
• Read: Book chapter 9.

Lecture 12: 15/10/2

• First test

Lecture 13: 17/10/2

• Midterm solutions.
• More on Delaunay triangulations.

Lecture 14: 22/10/2

• Analysis of randomized incremental Delaunay triangulation construction.
• Delaunay triangulation by lifting points on a paraboloid and computing the 3D convex hull.

Lecture 15: 24/10/2

• Voronoi diagrams.
• Read: Book chapter 7.

Lecture 16: 29/10/2

• Duality transforms:
  • Motivation: intersection of halfplanes
  • Point to line duality: (a,b) to y=ax+b
  • From the incidence property, derived line to point: y=cx+d to (-c,d)
  • Preserves:
    • Incidences
    • Above/below
    • vertical distance
  • Dual vision of
    • Vertical lines to points at infinity (homogeneous coordinates)
    • Collinear points
    • Halfplanes
    • Intersection of halfplanes to convex hull
  • Brief mention of higher dimension duality transforms, point to planes and Pluecker coordinates.
• Next time: Linear programming

Lecture 17: 31/10/2

• Linear Programming:
• Applicationn: Carving pumpkins.
• Definition, Simplex method (can be slow)
• Linear programming in R^1 in O(n)
• In R^2: Convex Hull -> O(n log n)
• In R^2: incremental -> O(n^2)
• In R^2: randomized incremental -> O(n)
• In R^d: randomized incremental -> O(d! n)
• Briefly: smallest enclosing circle
• Read: Textbook chapter 4

Lecture 18: 5/11/2

• Arrangements:
  • Definitions: vertices, edges, faces
  • Complexity: number of vertices, edges, faces
  • Data structure: DCEL
  • Construction: linesweep -> O(n^2 log n)
  • Construction: incremental
  • Zone theorem: complexity of a zone is O(n) => complexity incremental construction is O(n^2)
  • Read: Textbook chapter 8.
• Linear regression for n points:
  • Least squares, not robust
  • Thiel-Sen estimator: draw a line through each pair of points,
    • find the median of their slopes
    • The Thiel estimator is a line of that slope with at most n/2 points above and below it.
  • Computation: list all O(n^2) lines to find median slope -> O(n^2) time and space
  • Dual: n lines. Find median vertex according to x coordinate. Linesweep. O(n^2 log n) time and O(n) space.
  • Counting vertices to the left of a vertical line by counting inversions during sorting. O(n log n) time.
  • Read: Webpage by David Eppstein on robust regression. Read the "Median slope" paragraph for references to papers.
  • Read: On this Webpage by Jiri Matousek, you will find "Older lecture notes on incremental geometric algorithms and some algorithms for planar arrangements". Read chapter 10.2, p127, about slope selection.

Lecture 19: 7/11/2

• Vertex selection
  • Review of last time
  • Ranking a vertex (how many are to its left), deciding if the kth vertex is to the left or to the right of a vertical line (=vertical sidedness)
  • Counting vertices inside a vertical slab
  • Counting vertices -> generating a random vertex
  • Randomized selection of the kth vertex in O(n log^2 n)
• Ham-sandwich cuts
  • Bisectors of a set of points
  • Dual of a bisector, median level
  • Ham-sandwich cut = intersection of median levels in the dual, existence, odd intersections
  • vertical sidedness
  • O(n log^2 n) randomized algorithm

Lecture 20: 12/11/2

• Ham-sandwich cuts, Megiddo's linear time algorithm for the separated case.
• Kd-trees