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

[ Sweepline notes | BKOS Sweep Line ]

[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 Triangulation

The 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

[Project Summary]
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 Depth

The 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 Subdivisions

The original paper can be found here (CMU only).

 [Notes]
29 4/7

Orthogonal Range Search with kd-trees

See Chapter 5 in the book for a similar treatment.
30 4/9

Orthogonal Range Trees and Fractional Cascading

See 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 Dimensions

See 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