15-456: Computational Geometry

1 | 1/11 |
## The First Computational Geometers |
[Notes] | |

## Sorting |
||||

2 | 1/13 |
## Convex Hulls in 2D |
[Notes] | |

3 | 1/15 |
## Graham Scan, Predicates, and Lower Bounds |
[Notes] | |

1/18 |
## No Class: Martin Luther King Jr. Day |
|||

4 | 1/20 |
## 2D Random Incremental Convex Hull[ CH Intro ] |
[Notes] | |

5 | 1/22 |
## Line Segment Intersection using SweepLine |
[Notes] | |

6 | 1/25 |
## More SweepLines and Linear Predicates |
[Notes] | |

7 | 1/27 |
## Intro to Delaunay Triangulations |
[Notes] | |

8 | 1/29 |
## Delaunay Triangulation as Convex Hull |
[Notes] | |

9 | 2/1 |
## Random Incremental Delaunay TriangulationThe point location cost analysis in the next lecture. |
[Notes] | |

10 | 2/3 |
## Voronoi Diagrams |
[Notes] | |

11 | 2/5 |
## Data Structures for Planar Cell Complexes |
||

2/8 |
## No Class: Snow Day! |
|||

2/10 |
## No Class: Snow Day! |
|||

## Planar Graphs |
||||

12 | 2/12 |
## Intro to Planar Graphs |
[Notes] | |

13 | 2/15 |
## Embeddings of 3-Connected Planar Graphs |
||

14 | 2/17 |
## How to Draw a Graph (part 1) |
[Notes] | |

15 | 2/19 |
## How to Draw a Graph (part 2) |
[Notes] | |

16 | 2/22 |
## Overview of the course project |
||

17 | 2/24 |
## Linkages and Reciprocal Diagrams |
[Notes] | |

18 | 2/26 |
## The Maxwell-Cremona Correspondence |
[Notes] | |

19 | 3/1 |
## Steinitz's Theorem |
[Notes] | |

20 | 3/3 |
## Project session |
||

3/5 |
## No Class: Spring Break |
|||

## Selection |
||||

21 | 3/15 |
## Centerpoints |
[Notes] | |

22 | 3/17 |
## Depth levels and Tverberg's theorem |
[Notes] | |

3/19 |
## No Class: Geometry and Robotices Seminar in NSH 1305 |
|||

23 | 3/22 |
## Linear-time Centerpoints in the plane |
[Notes] | |

24 | 3/24 |
## Computing centerpoints in higher dimensions |
[Notes] | |

3/26 |
## No Class: Ketan Mulmuley on Geometric Complexity Theory in GHC 4307 |
|||

25 | 3/29 |
## Midterm |
||

26 | 3/31 |
## The Centervertex Theorem for Wedge DepthThe original paper can be found here, and the slides from the original conference talk can be found here. |
[Notes] | |

27 | 4/2 |
## Maximum Feasible Subsystem and the Hardness of Testing Tukey Depth |
[Notes] | |

## Geometric Search |
||||

28 | 4/5 |
## Searching Planar SubdivisionsThe original paper can be found here (CMU only). |
[Notes] | |

29 | 4/7 |
## Orthogonal Range Search with kd-treesSee Chapter 5 in the book for a similar treatment. |
||

30 | 4/9 |
## Orthogonal Range Trees and Fractional CascadingSee Chapter 5 in the book for a similar treatment. |
||

31 | 4/12 |
## Nearest Neighbor Search |
[Notes] | |

32 | 4/14 |
## Approximate Nearest Neighbors in Quadtrees |
||

4/16 |
## No Class: Carnival! |
|||

33 | 4/19 |
## Yet more Quadtrees |
[Notes] | |

34 | 4/21 |
## Halfspace Discrepancy |
[Notes] | |

35 | 4/23 |
## More on Projective Duality |
[Notes] | |

## Optimization |
||||

36 | 4/26 |
## Linear Programming in Low DimensionsSee chapter 4 in the book for notes. |
||

37 | 4/28 |
## Polytopes |
[Notes] | |

38 | 4/30 |
## Project Presentations |
||

39 | 5/7 |
## final Exam 5:30-8:30 |