Date  Topics and References  Scribe notes 
Jan 18 
 Twodimensional convex hulls:

 convexity, clockwise/counterclockwise test, general position, exact arithmetic
 Jarvis march ("selection sort")  O(nh)
 Preparata and Hong's partitionhull ("quicksort")  O(n log n)
 Graham's scan («das Dreigroschenalgorithmus»)  O(n log n)
 Toussaint's mergehull ("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 twodimensional convex hulls:

 Graham and Yao's sweepline  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
[csypddpo97 §3]  O(n log h)
 Bhattacharya and Sen's pruned randomized quickhull
[bsspoos97]  O(n log h)
 Wenger's pruned randomized quickhull
[wrqh97]  O(n log h)
 General references: [Dutch, ch.1], [Joe, ch.3]

[Miranda Callahan] 
Jan 25 
 The end of twodimensional convex hulls:

 Chan's shatterhull [coosch96] 
O(n log h)
 Voronoi diagrams

 basic definitions
 building one region by (dual) Jarvis march
 Pointline duality


Primal  Dual  Algebra 
point p = (a,b) 
line p*: y = axb 
line l: y = AxB 
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
 depthfirst search ("same" as one cell at a time)  O(n^{2})
 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: graphtheoretic 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(n^{2})
 Knuth, Guibas, and Sharir's randomized incremental flipping  O(n log n)
 Fortune's sweepline  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[ Sum_{triangles t created in ith phase} k(t) ] < 12n/i
 References: [Dutch 9.4], [zbacdt99]
 Lifting to 3d convex hulls

 The paraboloid lifting map (x, y) > (x, y, x^{2}+y^{2})
 incircle > tetrahedron orientation
 Delaunay triangulation > lower convex hull
 Voronoi diagram > upper envelope of tangent planes
 graphtheoretic 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 worstcase optimal point location

 First approximation (naive "slab" method): O(n^{2}) space,
2 log n + O(1) query time.
 Second approximation: O(n^{3/2}) space, 3/2 log n + O(1) query time
 kth approximation: O(n^{1+1/k}) space, (1+1/k)log n + o(log n) query time
 k = 2^{sqrt{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(n^{3}) and
Omega(n^{2})
 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(n^{2}) 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 log^{2}n + k) expected or
O((n+k) log n) worst case in 3d
 Chazelle's Omega(n^{2}) lower bound in 3d
 Line arrangements:

 Definitions: vertex, edge, facet
 Analysis: (n choose 2) vertices, n^{2} edges,
(n choose 2) + n + 1 facets
 O(n^{2} log n) algorithms: sweep line, sort vertices along each line
 O(n^{2}) 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 