CS 497: Computational Geometry

Lecture schedule

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: Convex Hulls by Alejo Hausner Graham's scan, Jarvis march, and quickhull Convex Hull Algorithms by Tim Lambert incremental, gift-wrapping, divide and conquer, and quickhull; also in 3D!	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: Voronoi Sweeping Algorithm by Hartmut Liefke very nice animation of Fortune's sweep algorithm Delaunay Triangulation demonstration by Conglin Lu anmiates Guibas and Stolfi's incremental flipping algorithm; Delaunay looks better
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: Finding Delaunay Triangulations Using 3D Convex Hulls by Daniel Mark Abrahams-Gessel very nice animation of the lifting map Delaunay Triangulation Algorithms by Tim Lambert incremental, gift-wrapping, divide and conquer, and quickhull as Delaunay algorithms
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

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