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:
 The Cross
Product and applications.
 Convexity:
definition.
 Convex Hull
CH(S) of a finite set S of points.
 Read:
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:
Lecture 3: 12/9/2
 Course projects.
 MergeHull, merging two convex polygons.
 Lower bounds:
 Adversary arguments.
 Reductions.
 Algebraic decision trees, DobkinLipton's theorem
 Read: Michiel Smid's lecture notes on lower bounds.
Lecture 4: 17/9/2 (covered by
Greg Aloupis)
Lecture 5: 19/9/2 (covered by
Greg Aloupis)
 Two ears theorem, method for finding two ears.
 Proof that triangulation is always possible (earcutting 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:
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 starshaped polygons
 DobkinLipton (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
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
 ThielSen 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)
 Hamsandwich cuts
 Bisectors of a set of points
 Dual of a bisector, median level
 Hamsandwich 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