Schedule

Please keep in mind that this is very preliminary and will change.

Day Date Instr Topics Covered Notes and Readings
Tue Jan 14 Gary Lecture 1: Introduction, The Line Intersection Problem using Sweepline ClassNotes -- BKOS Chap 2 -- Intro Notes -- SweepLine Notes
Thu Jan 16 Gary Lecture 2: 2D Convex Hull: Divide-and-Conquer and Random Incremantal ClassNotes -- 2D Convex Notes
Tue Jan 21 Gary Lecture 3: 2D-LP and Random Incremental ClassNotes -- BKOS Chap 4
Thu Jan 23 Gary Lecture 4: Geometric Transforms ClassNotes -- HW1 out
Tue Jan 28 Snow Day - No Class
Thu Jan 30 Gary Lecture 5: Geometric Transforms Continued
Tue Feb 04 Gary Lecture 6: Planar Point Location; Trapezoidation ClassNotes --BKOS Chap 6

[Mount Chap 9 & 10 ]

Thu Feb 06 Gary Lecture 7: Traps and Chernoff Bounds HW2 out -- ClassNotes --BKOS Chap 6

[Mount Chap 9 & 10 ]

Tue Feb 11 Gary Lecture 8: Triangulating a Polygon ClassNotes -- BKOS Chap 3
Thu Feb 13 Gary Lecture 9: Homework 1 Presentations
Tue Feb 18 Gary Lecture 10: Radon, Carathéodory, and Helly's Theorems ClassNotes --Gil Kalai's Bolg
Thu Feb 20 Gary Lecture 11: Approximate Centerpoints ClassNotes-- Paper
Tue Feb 25 Gary Lecture 12: Colorful Caratheodory and Tverberg Partition ClassNotes-- Gil Kalai's Bolg

HW3 out

Thu Feb 27 Gary Lecture 13: Representing Topological Information ClassNotes -- Brisson-93 -- Cell-Chains
Tue Mar 04 Gary Lecture 14: 2D-Closest Pair using Hashing ClassNotes -- Har-Peled-Chap-1
Thu Mar 06 Gary Lecture 15: VC dimension and epsilon-nets ClassNotes -- Har-Peled-Chap-5
Tue Mar 11 Spring Break - No Class
Thu Mar 13 Spring Break - No Class
Tue Mar 18 Gary Lecture 16: VC dimension and epsilon-nets continued ClassNotes -- Har-Peled-Chap-5

HW3 due

Thu Mar 20 Gary Lecture 17: 2D Mesh Generation: Quadtree ClassNotes -- BKOS Chap 14--Har-Peled-Chap-12
Tue Mar 25 Gary Lecture 18: Delaunay Refinement ClassNotes-- Wikipedia Page
Thu Mar 27 Gary Lecture 19: Delaunay Refinement II
Tue Apr 01 Gary Lecture 20: Convexifying a Polygon (Part 1) ClassNotes -- Connelly Demaine and Rote -- Connelly and Demaine --- Don Sheehy Slides
Thu Apr 03 Gary Lecture 21: Convexifying a Polygon (Part 2)
Tue Apr 08 Spring Carnival - No Class
Thu Apr 10 Spring Carnival - No Class
Tue Apr 15 Gary Lecture 22: Graph Rigidity and Pseudo-Trianglualtions
Thu Apr 17 Gary Lecture 23: Brunn-Minkowski ClassNotes--Har-Peled-Chap-19
Tue Apr 22 Gary Lecture 24:
Thu Apr 24 Gary Lecture 25:
Tue Apr 29 Gary Lecture 26:
Thu May 01 Gary Lecture 27: