# 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]
• 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)
• 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!
• 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

### References

 [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