CS 497: Computational Geometry

Lecture schedule

[Sorry this has gotten so out of date. I'll backfill the missing stuff soon. Honest.]

Date Topics and References Scribe notes
Jan 18
Two-dimensional convex hulls:
  • convexity, clockwise/counterclockwise test, general position, exact arithmetic
  • Jarvis march ("selection sort") - O(nh)
  • Preparata and Hong's partition-hull ("quicksort") - O(n log n)
  • Graham's scan («das Dreigroschenalgorithmus») - O(n log n)
  • Toussaint's merge-hull ("mergesort") - O(n log n)
  • Edelsbrunner's incremental insertion ("insertion sort") - O(n log n)
  • General references: [Dutch, ch.1], [Joe, ch.3]
  • WWW links:
  • notes1.ps
    [Miranda Callahan]
    Jan 20
    More two-dimensional convex hulls:
  • Graham and Yao's sweep-line - O(n log n)
  • Clarkson and Shor's randomized incremental - O(n log n)
  • Floyd's "quickhull" - O(nh)
  • Kirkpatrick and Seidel's marriage before conquest - O(n log h)
  • Chan, Snoeyink, and Yap's prune and search [csy-pddpo-97 §3] - O(n log h)
  • Bhattacharya and Sen's pruned randomized quickhull [bs-spoos-97] - O(n log h)
  • Wenger's pruned randomized quickhull [w-rqh-97] - O(n log h)
  • General references: [Dutch, ch.1], [Joe, ch.3]
  • [Miranda Callahan]
    Jan 25
    The end of two-dimensional convex hulls:
  • Chan's shatter-hull [c-oosch-96] - O(n log h)
    Voronoi diagrams
  • basic definitions
  • building one region by (dual) Jarvis march
    Point-line duality
  • Primal Dual Algebra
    point p = (a,b) line p*: y = ax-b
    line l: y = Ax-B point l* = (A,B)
    p above l l* above p* b+B > Aa
    p below l l* below p* b+B < Aa
    p on l l* below p* b+B = Aa
    l = line though p and q l* = intersection of p* and q*
    p,q,r colinear p*,q*,r* concurrent det[p q r] = 0
    p,q,r counterclockwise p*,q*,r* counterclockwise
    (around finite triangle)
    det[p q r] > 0
    convex hull of points outer envelope of lines
    upper convex hull lower envelope
    lower convex hull upper envelope
    hull vertex envelope edge
    hull edge envelope vertex
    vertical line point at infinity
    line at infinity point at vertical infinity
  • WWW link: Point/Line Duality by Fred Henle
  • [Holly Wilper]
    Jan 27
    Constructing Voronoi diagrams:
  • incircle test
  • depth-first search ("same" as one cell at a time) - O(n2)
  • Shamos and Hoey's divide and conquer - O(n log n)
  • WWW link: Delaunay Triangulation, and more ... by Chenghui Luo
    anmiates Shamos and Hoey's divide and conquer algorithm
    Delaunay triangulations
  • definition: graph-theoretic dual of Voronoi diagram
  • Theorem: A triangulation is Delaunay iff every triangle has an empty circumcircle.
  • An edge is locally Delaunay if the circum circle of the triangle on one side excludes the apex of the triangle on the other side.
  • Theorem: A triangluation is Delaunay iff every edge is locally Delaunay.
  • Feb 1
    Constructing Voronoi diagrams and Delaunay triangulations:
  • Green and Sibson's incremental - O(n2)
  • Knuth, Guibas, and Sharir's randomized incremental flipping - O(n log n)
  • Fortune's sweep-line - O(n log n)
  • WWW links:
  • Feb 3
    Randomized incremental: maintaining conflicts
  • "Fundamental theorem of combinatorics": Nested sums can be done in either order
  • Configuration spaces
  • E[ Sumtriangles t created in ith phase k(t) ] < 12n/i
  • References: [Dutch 9.4], [z-bacdt-99]
    Lifting to 3d convex hulls
  • The paraboloid lifting map (x, y) -> (x, y, x2+y2)
  • incircle -> tetrahedron orientation
  • Delaunay triangulation -> lower convex hull
  • Voronoi diagram -> upper envelope of tangent planes
  • graph-theoretic Delaunay/Voronoi duality is really projective point/plane duality!
  • WWW links:
  • Feb 8 No class this week
    Feb 10
    Feb 15
    3d convex hull algorithms:
  • Gift wrapping (= DFS algorithm for Voronoi diagrams)
  • Preparata and Hoey (= Shamos and Hoey's divide and conquer)
  • Randomized incremental flipping
  • Feb 17
    Feb 22
    Feb 24
    Feb 29
    Mar 2
    Mar 7
    Adamy and Seidel's worst-case optimal point location
  • First approximation (naive "slab" method): O(n2) space, 2 log n + O(1) query time.
  • Second approximation: O(n3/2) space, 3/2 log n + O(1) query time
  • kth approximation: O(n1+1/k) space, (1+1/k)log n + o(log n) query time
  • k = 2sqrt{log n} --> log n + o(log n) query time
  • The real thing: log n + 2sqrt{log n} + (1/2)log log n + O(1) query time
  • The lower bound model: trapezoidal serach graphs
  • Mar 9
    BSP trees:
  • Definitions: cutting hyperplane, cell, autopartition
  • "Obvious" randomized incremental autopartition: For each segment, cut every cell it intersects
    • O(n log n) expected size in 2d
    • Complexity in 3d is open: best bounds are O(n3) and Omega(n2)
  • Modified randomized incremental autopartition: For each segment, cut every cell in which its line crosses an uninserted segment, and then make all available free cuts
    • O(n log n) expected size in 2d
    • O(n2) expected size in 3d
  • Mar 14 Spring break -- No class this week
    Mar 16
    Mar 21
    More on BSP trees:
  • Cylindrical BSPs: O(n log n) in 2d; O(n log2n + k) expected or O((n+k) log n) worst case in 3d
  • Chazelle's Omega(n2) lower bound in 3d
    Line arrangements:
  • Definitions: vertex, edge, facet
  • Analysis: (n choose 2) vertices, n2 edges, (n choose 2) + n + 1 facets
  • O(n2 log n) algorithms: sweep line, sort vertices along each line
  • O(n2) incremental algorithm
  • The Zone Theorem: The zone of any line in any arrangment of n lines has at most 6n edges (assuming general position).
  • Mar 23
    Mar 28
    Mar 30
    Apr 4
    Apr 6
    Apr 11
    Apr 13
    Apr 18
    Apr 20
    Apr 25
    Apr 27
    May 2


    [bs-spoos-97] Binay Bhattacharya and Sandeep Sen. On a simple, practical, optimal, output-sensitive randomized planar convex hull algorithm. Journal of Algorithms 25:173-193, 1997.
    [c-oosch-96] Timothy Chan. Optimal output-sensitive convex hull algorithms in two and three dimensions. Discrete & Computational Geometry 16:361-368, 1996.
    [csy-pddpo-97] Timothy Chan, Jack Snoeyink, and Chee Yap. Primal dividing and dual pruning: Output-sensitive construcion of 4-d polytopes and 3-d Voronoi diagrams. Discrete & Computational Geometry 18: 433-454, 1997.
    [w-rqh-97] Rephael Wenger. Randomized Quick Hull. Algorithmica 17:322-329, 1997.
    [z-bacdt-99] Afra Zomorodian. Backwards analysis and constructing Delaunay trianglations. Slides from "Randomized Algorithms" class taught by Shang-Hua Teng, Spring 1999.

    CS 497 (Spring 2000) - Jeff Erickson (jeffe@cs.uiuc.edu) 21 Mar 2000