15-456/852: Comp Geo

Fall 2017

Day | Date | Instr | Topics Covered | Notes and Readings |
---|---|---|---|---|

Mon | Aug 28 | Gary | Lecture 1: Short Class for Introductions | |

Wed | Aug 30 | No Class Yet - No Class |
||

Fri | Sep 01 | Gary | Lecture 2: Preclass lecture on linear algebra | [ClassNotes] pdf -note |

Mon | Sep 04 | Labor Day - No Class |
||

Wed | Sep 06 | Gary | Lecture 3: Introduction, The Line Intersection Problem using Sweepline | [ClassNotes]
pdf
-note -- BKOS Chap 2 -- Intro Notes -- SweepLine Notes |

Fri | Sep 08 | Gary | Lecture 4: Backwards Analysis of QuickSort: 2D Convex Hull: Reduction from sorting; Divide-and-Conquer |
[ClassNotes-Backwards Analysis]
pdf
-note [ClassNotes] pdf -note -- 2D Convex Notes |

Mon | Sep 11 | Gary | Lecture 5: 2D Convex Hull: Random Incremental | 2D Convex Notes |

Wed | Sep 13 | Gary | Lecture 6: 2D-LP and Random Incremental | [ClassNotes]
pdf
-note -- BKOS Chap 4 |

Fri | Sep 15 | Gary | Lecture 7: 2D-LP and Random Incremental Continued & Checking for Unboundedness | |

Mon | Sep 18 | Gary | Lecture 8: Geometric Transforms | [ClassNotes]
pdf
-note -- Doru Balcan's Notes |

Wed | Sep 20 | Gary | Lecture 9: Geometric Transforms Continued | |

Fri | Sep 22 | Gary | Lecture 10: Planar Point Location; Trapezoidation | [ClassNotes]
pdf
-note BKOS Chap 6 [Mount Chap 9 & 10 ] |

Mon | Sep 25 | Gary | Lecture 11: Planar Point Location; Trapezoidation Continued | [ClassNotes]
pdf
-note BKOS Chap 6 [Mount Chap 9 & 10 ] |

Wed | Sep 27 | Gary | Lecture 12: Traps and Chernoff Bounds | [ClassNotes]
pdf
-note BKOS Chap 6 [Mount Chap 9 & 10 ] |

Fri | Sep 29 | Gary | Lecture 13: Triangulating a Polygon | [ClassNotes]
pdf
-note BKOS Chap 3 |

Mon | Oct 02 | Gary | Lecture 14: Radon, Carathéodory, and Helly's Theorems | [ClassNotes]
pdf
-note -- Gil Kalai's Blog |

Wed | Oct 04 | Gary | Lecture 15: Radon, Carathéodory, and Helly's Theorems Continued | [ClassNotes]
pdf
-note -- Gil Kalai's Blog |

Fri | Oct 06 | Gary | Lecture 16: Centerpoints and Approximate Centerpoints | [ClassNotes]
pdf
-note -- Paper |

Mon | Oct 09 | Gary | Lecture 17: Colorful Carathéodory and Tverberg Partition | [ClassNotes]
pdf
-note -- Gil Kalai's Blog -- Related Reading |

Wed | Oct 11 | Gary | Lecture 18: Homework 1 Presentations | |

Fri | Oct 13 | Gary | Lecture 19: Homework 1 Presentations continued | |

Mon | Oct 16 | Gary | Lecture 20: Representing Topological Information | [ClassNotes]
pdf
-note -- Cell-Chains |

Wed | Oct 18 | Gary | Lecture 21: Representing Topological Information and Decidability and Topology | OldClassNotes -- Brisson-93 -- Cell-Chains |

Fri | Oct 20 | Mid-Semester Break - No Class |
||

Mon | Oct 23 | Gary | Lecture 22: 2D-Closest Pair using Hashing | OldClassNotes -- Har-Peled-Chap-1 |

Wed | Oct 25 | Gary | Lecture 23: Approximate Nearest Neighbor | OldClassNotes -- Har-Peled-Chap-17 |

Fri | Oct 27 | Gary | Lecture 24: Approximate Nearest Neighbor Continued | OldClassNotes -- Har-Peled-Chap-17 |

Mon | Oct 30 | Gary | Lecture 25: 2D Mesh Generation: Quadtree | OldClassNotes -- BKOS Chap 14 --Har-Peled-Chap-12 |

Wed | Nov 01 | Gary | Lecture 26: Delaunay Refinement | OldClassNotes -- Wikipedia Page |

Fri | Nov 03 | Jakub | Lecture 27: Homework 2 Presentations | |

Mon | Nov 06 | Gary | Lecture 28: Delaunay Refinement II | |

Wed | Nov 08 | Gary | Lecture 29: Delaunay Refinement III | |

Fri | Nov 10 | Gary | Lecture 30: VC dimension and epsilon-nets | OldClassNotes -- Har-Peled-Chap-5 |

Mon | Nov 13 | Gary | Lecture 31: Homework 3 Presentations | |

Wed | Nov 15 | Gary | Lecture 32: VC dimension and epsilon-nets II | OldClassNotes -- Har-Peled-Chap-5 |

Fri | Nov 17 | Gary | Lecture 33: VC dimension and epsilon-nets III | OldClassNotes -- Har-Peled-Chap-5 |

Mon | Nov 20 | Gary | Lecture 34: Bezier Curves and Bossoms | OldClassNotes -- Chapter 3 -- Chapter 4 -- Chapter 5 |

Wed | Nov 22 | Thanksgiving Holiday - No Class |
||

Fri | Nov 24 | Thanksgiving Holiday - No Class |
||

Mon | Nov 27 | Gary | Lecture 35: B-Splines | OldClassNotes -- Chapter 8 |

Wed | Nov 29 | Gary | Lecture 36: Recursive Subdivisions | OldClassNotes -- Chapter 21 -- Evaluation of Loop |

Fri | Dec 01 | Gary | Lecture 37: Brunn-Minkowski | OldClassNotes --Har-Peled-Chap-19 |

Mon | Dec 04 | Gary | Lecture 38: Johnson Lindenstrauss | OldClassNotes --Har-Peled-Chap-19 |

Wed | Dec 06 | Gary | Lecture 39: Johnson Lindenstrauss | OldClassNotes --Har-Peled-Chap-19 |

Fri | Dec 08 | Gary | Lecture 40: Generating a Distribution: Exponential and Normal | OldClassNotes |