Our notes from lecture will be made available on Canvas under the Files section shortly after each lecture: [link to notes]
Lecture topics, related textbook chapters, and recording links will be provided below, along with any additional materials (other readings, code examples, etc.) Future dates are subject to change.
01: 8/28 Introduction, Chapter 1.
Geometric Data Structures for Similarity Search (Chapter 5)
02: 8/30 Nearest Neighbor Queries on kd-trees
03: 9/4 NN and Orthogonal Range Queries on kd-trees
04: 9/6 Orthogonal Range Queries on kd-trees II (Project 1 out)
05: 9/11 Orthogonal Range Queries on Range Trees
06: 9/13 Range Tree Analysis and applications
Convex Hulls (Chapter 1)
07: 9/18 Convex Hulls [recording]
08: 9/20 Graham Scan and Jarvis March [Graham wiki] [Jarvis wiki] (Project 1 in)
09: 9/25 Chan’s Algorithm [Chan wiki]
Map Overlays (Chapter 2)
10: 9/27 Segment Intersection (Project 2 out)
11: 10/2 Segment Intersection II
12: 10/4 Planar Subdivisions + DCEL
13: 10/9 Computing Overlay Edges
14: 10/11 Computing Overlay Faces (Project 2 in)
15: 10/16 Original Faces, Boolean Operations, Robustness
Windowing Queries (Chapter 10)
16: 10/18 Windowing Queries for Axis-Parallel Segments (Interval Trees) (Project 3 out)
17: 10/23 Windowing Queries for Non-Crossing Segments (Segment Trees)
18: 10/25 Segment Trees II
Delaunay Triangulations and Voronoi Diagrams
19: 10/30 Delaunay Triangulations I
20: 11/1 Delaunay Triangulations II (Project 3 in)
21: 11/6 Delaunay Triangulations III & Point Location via Segment Trees
22: 11/8 Voronoi Diagrams I (Project 4 out)
23: 11/13 Voronoi Diagrams II
Combinatorial Robot Motion Planning
24: 11/15 Combinatorial Motion Planning I
25: 11/20 Combinatorial Motion Planning II
26: 11/22 Heuristical/Randomized Motion Planning
27: 11/27 FALL BREAK (Project 5 out)
28: 11/29 FALL BREAK
29: 12/4 RMP II
30: 12/6 LDOC, Wrapping Up (Projects 4 & 5 in)
