Schedule

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

Day Date Instr Topics Covered Notes and Readings
Mon Aug 31 Gary Lecture 1: Introduction, The Line Intersection Problem using Sweepline ClassNotes -- BKOS Chap 2 -- Intro Notes -- SweepLine Notes
Wed Sep 02 Gary Lecture 2: 2D Convex Hull: Reduction from sorting; Divide-and-Conquer ClassNotes -- 2D Convex Notes
Fri Sep 04 Gary Lecture 3: 2D Convex Hull: Random Incremental ClassNotes -- 2D Convex Notes
Mon Sep 07 Labor Day - No Class
Wed Sep 09 Gary Lecture 4: Geometric Transforms ClassNotes -- Doru Balcan's Notes
Fri Sep 11 Gary Lecture 5: Geometric Transforms Continued
Mon Sep 14 Gary Lecture 6: 2D-LP and Random Incremental ClassNotes -- BKOS Chap 4
Wed Sep 16 Gary Lecture 7: 2D-LP and Random Incremental Continued & Checking for Unboundedness
Fri Sep 18 Gary Lecture 8: Planar Point Location; Trapezoidation ClassNotes -- BKOS Chap 6

[Mount Chap 9 & 10 ]

Mon Sep 21 Gary Lecture 9: Traps and Chernoff Bounds ClassNotes -- BKOS Chap 6

[Mount Chap 9 & 10 ]

Wed Sep 23 Gary Lecture 10: Triangulating a Polygon ClassNotes -- BKOS Chap 3
Fri Sep 25 Gary Lecture 11: Radon, Carathéodory, and Helly's Theorems ClassNotes -- Gil Kalai's Blog
Mon Sep 28 Gary Lecture 12: Radon, Carathéodory, and Helly's Theorems Continued ClassNotes -- Gil Kalai's Blog
Wed Sep 30 Gary Lecture 13: Approximate Centerpoints ClassNotes -- Paper
Fri Oct 02 Gary Lecture 14: Colorful Carathéodory and Tverberg Partition ClassNotes -- Gil Kalai's Blog
Mon Oct 05 Gary Lecture 15: Homework 1 Presentations
Wed Oct 07 Gary Lecture 16: Homework 1 Presentations continued
Fri Oct 09 Gary Lecture 17: Representing Topological Information ClassNotes -- Brisson-93 -- Cell-Chains
Mon Oct 12 Gary Lecture 18: Representing Topological Information and Decidability and Topology ClassNotes -- Brisson-93 -- Cell-Chains
Wed Oct 14 Gary Lecture 19: 2D-Closest Pair using Hashing ClassNotes -- Har-Peled-Chap-1
Fri Oct 16 Gary Lecture 20: Approximate Nearest Neighbor ClassNotes -- Har-Peled-Chap-17
Mon Oct 19 Gary Lecture 21: Approximate Nearest Neighbor Continued ClassNotes -- Har-Peled-Chap-17
Wed Oct 21 Gary Lecture 22: 2D Mesh Generation: Quadtree ClassNotes -- BKOS Chap 14 --Har-Peled-Chap-12
Fri Oct 23 Mid-Semester Break - No Class
Mon Oct 26 Gary Lecture 23: Delaunay Refinement ClassNotes -- Wikipedia Page
Wed Oct 28 Jakub Lecture 24: Homework 2 Presentations
Fri Oct 30 Gary Lecture 25: Delaunay Refinement II
Mon Nov 02 Gary Lecture 26: Delaunay Refinement III
Wed Nov 04 Gary Lecture 27: VC dimension and epsilon-nets ClassNotes -- Har-Peled-Chap-5
Fri Nov 06 Gary Lecture 28: Homework 3 Presentations
Mon Nov 09 Gary Lecture 29: VC dimension and epsilon-nets II ClassNotes -- Har-Peled-Chap-5
Wed Nov 11 Gary Lecture 30: VC dimension and epsilon-nets III ClassNotes -- Har-Peled-Chap-5
Fri Nov 13 Gary Lecture 31: Bezier Curves and Bossoms ClassNotes -- Chapter 3 -- Chapter 4 -- Chapter 5
Mon Nov 16 Gary Lecture 32: B-Splines ClassNotes -- Chapter 8
Wed Nov 18 Gary Lecture 33: Recursive Subdivisions ClassNotes -- Chapter 21 -- Evaluation of Loop
Fri Nov 20 Gary Lecture 34: Brunn-Minkowski ClassNotes --Har-Peled-Chap-19
Mon Nov 23 Gary Lecture 35: Johnson Lindenstrauss ClassNotes --Har-Peled-Chap-19
Wed Nov 25 Thanksgiving Holiday - No Class
Fri Nov 27 Thanksgiving Holiday - No Class
Mon Nov 30 Gary Lecture 36: Johnson Lindenstrauss ClassNotes --Har-Peled-Chap-19
Wed Dec 02 Gary Lecture 37: Generating a Distribution: Exponential and Normal ClassNotes
Fri Dec 04 Gary Lecture 38: Convexifying a Polygon (Part 1) ClassNotes -- Connelly Demaine and Rote -- Connelly and Demaine -- Don Sheehy Slides
Mon Dec 07 Gary Lecture 39: Convexifying a Polygon (Part 2)
Wed Dec 09 Gary Lecture 40: TBA
Fri Dec 11 Gary Lecture 41: Last Lecture