Tue, Jan. 9th 
Introduction and administrivia, convex hulls, simplifying assumptions, modified Graham's
scan [Graham '72, Andrew '79]

3Marks Preface, 1; Mount 1, 3;
lecture notes


Thur, Jan. 11th 
More convex hulls, lower bound, Jarvis's march (gift wrapping) ['73], output sensitivity,
Chan's algorithm ['96]

Mount 4;
lecture notes


Tue, Jan. 16th 
Line segment intersection, plane sweep [Bentley, Ottmann '79]

3Marks 2–2.1; Mount 5;
lecture notes


Thur, Jan. 18th 
(Monotone) polygon triangulation [Garey et al. '78], doublyconnected edge lists

3Marks 3; Mount 6;
lecture notes


Tue, Jan. 23rd 
Monotone polygon decomposition [Lee, Preparata '77] (for triangulation), halfplane
intersection, pointline duality

3Marks 3.2, 4.2, 8.2, 11.4; Mount 6, 7;
lecture notes

Homework 1 released. 
Thur, Jan. 25th 
Halfplane intersection and pointline duality continued, linear programming, randomized
incremental construction [Seidel '91]

3Marks 4, 11.4; Mount 8;
lecture notes


Tue, Jan. 30th 
Linear programming and backward analysis for randomized incremental construction, orthogonal
range searching via kdtrees

3Marks 5–5.2; Mount 31;
lecture notes


Thur, Feb. 1st 
Orthogonal range searching continued, kdtrees, orthogonal range trees

3Marks 5; Mount 31–32;
lecture notes


Tue, Feb. 6th 
Trapezoidal maps, their construction [Mulmuley '90; Seidel '91];
lecture notes

3Marks 6; Mount 9

Homework 1 due (solutions).
Homework 2 released.

Thur, Feb. 8th 
Trapezoidal maps continued, planar point location, tail bounds (bonus) [Mulmuley '90; Seidel
'91];
lecture notes

3Marks 6; Mount 10


Tue, Feb. 13th 
Voronoi diagrams, Fortune's algorithm ['87]

3Marks 7–7.2; Mount 11;
lecture notes


Thur, Feb. 15th 
Delaunay triangulations, uses and properties

3Marks 9–9.2; Mount 12;
lecture notes


Tue, Feb. 20th 
Delaunay triangulations, randomized incremental construction

3Marks 9.3–9.4; Mount 13;
lecture notes


Thur, Feb. 22nd 
Line arrangements, construction, zone theorem

3Marks 8.3; Mount 14;
lecture notes

Homework 2 due (solutions).

Tue, Feb. 27th 
Line arrangement applications, sorting angular sequences, narrowest kcorridor, halfplane
discrepancy, plane sweeps

3Marks 8; Mount 15;
lecture notes


Thur, Mar. 1st 
Delaunay triangulations and 3D lower convex hulls, Voronoi diagrams and 3D upper envelopes

3Marks 11.0, 11.5; Mount 16;
lecture notes

See 3Marks 11.1–11.3 for an algorithm to construct 3D convex hulls.

Tue, Mar. 6th 
Robot motion planning, configuration spaces, Minkowski sums

3Marks 13; Mount 20;
lecture notes

Project proposals due.
Homework 3 released.

Thur, Mar. 8th 
Robot motion planning continued, visibility graphs, shortest paths

3Marks 15; Mount 29;
lecture notes


Tue, Mar. 13th 
No class; enjoy Spring Break!



Thur, Mar. 15th 
No class; enjoy Spring Break!



Tue, Mar. 20th 
Curve similarity, Hausdorff distance, Fréchet distance

Lecture notes


Thur, Mar. 22nd 
Approximation algorithms, kcenter

Erickson
31.2, 31.8–31.9;
lecture notes

Homework 3 due (solutions).
Homework 4 released.

Tue, Mar. 27th 
Well separated pair decompositions (WSPDs), construction of WSPDs

Mount 17;
lecture notes


Thur, Mar. 29th 
Applications of WSPDs

Mount 18;
lecture notes


Tue, Apr. 3rd 
Geometric sampling, VCdimension

Mount 19;
lecture notes


Thur, Apr. 5th 
Geometric sampling continued, learning a shape, geometric set cover and hitting set

Mount 19;
lecture notes

Homework 4 due (solutions).

Tue, Apr. 10th 
Metrics, embeddings, JohnsonLindenstrauss "lemma", Bourgain’s theorem

An elementary proof of
a theorem of Johnson and Lindenstrauss.
Sanjoy Dasgupta and Anupam Gupta.
Journal Random Structures & Algorithms, 22(1):60–65, 2003;
lecture notes


Thur, Apr. 12th 
Locality sensitive hashing

Munagala;
lecture notes


Tue, Apr. 17th 
Project presentations



Thur, Apr. 19th 
More project presentations



Tue, Apr. 24th 
Yet more project presentations



Thur, Apr. 26th 
Project presentations, course evaluations



Tue, May 1st 
Good luck on your finals!



Thur, May 3rd 
You're almost done!


Project reports due.
