Computational Geometry

CS 498 TC, Spring 2021

Main  ❖  Syllabus  ❖  Schedule  ❖  Resources

Polygons

Tue Jan 26

What is computational geometry?
Planar convex hulls: Jarvis' March (gift-wrapping)
[pre-scribbles, scribbles, video —  Mount 1–2, BGHW 4.3–4.5, BCKO 1, Jeff's old notes]

Thu Jan 28

More planar convex hulls: Graham's Scan (greedy local repair), Chan's algorithm (shattering)
[pre-scribbles, scribbles, video —  Mount 2, BGHW 4.6–4.8, BCKO 1, Jeff's old notes]

Tue Feb 2

Projective duality: Upper envelope of lines (merge-envelope and selection-envelope), new glasses
[pre-scribbles, scribbles, video —  Mount 6, BCKO 8.2]

Thu Feb 4

Segment intersection I: Detecting any intersections, plane sweep algorithm
[pre-scribbles, scribbles, video —  Mount 4, BCKO 2, BGHW A]

Tue Feb 9

Segment intersection II: Finding all $k$ intersecting pairs in $O((n+k)\log n)$ time, finding all $I$ intersection points in $O((n+I)\log n)$ time
[pre-scribbles, scribbles, video —  Mount 5, BCKO 2, BGHW A]

Thu Feb 11

Polygon triangulation: $O(n^2)$ time via diagonal divide-and-conquer; $O(n \log n)$ time via trapezoidal decompositions (plane sweep, boring diagonals, monotone mountains)
[scribbles, video —  Mount 4, BCKO 3, BGHW 3.2, Jeff's topology notes]

Mon Feb 15

Homework 1 due 8pm

Tue Feb 16

— no lecture —

Wed Feb 17

Spring break, Day 1

Thu Feb 18

Point-in-polygon testing and winding numbers

[ pre-scribbles, scribbles, video —  Jeff's topology notes on polygons and winding, Brushwood 2009, Maverick 2012]

Planar Maps

Tue Feb 23

Definitions, data structures, and Euler's formula

Thu Feb 25

Trapezoidal decompositions: Plane sweep (again) and randomized incremental con­struc­tions

Mon Mar 1

Homework 2 due 8pm

Tue Mar 2

Point location (randomized incremental history)

Thu Mar 4

Polygon triangulation redux

Mon Mar 8

Midterm due 10pm

Tue Mar 9

Voronoi diagrams, Delaunay triangulations, and 3d convex hulls

Thu Mar 11

Voronoi / Delaunay algo­rithms

Tue Mar 16

More Voronoi / Delaunay algorithms (Beyond the Planet of the Convex Hulls)

Thu Mar 18

Voronoi / Delaunay applications: Interpolation, post-office problem

Mon Mar 22

Homework 3 due 8pm

Tue Mar 23

— No lecture —

Wed Mar 24

Spring break, day 2

Thu Mar 25

[slack]

[TBA]

Tue Mar 30

[TBA]

Thu Apr 1

[TBA]

Mon Apr 5

Homework 4 due 8pm

Tue Apr 6

[TBA]

Thu Apr 8

[TBA]

Tue Apr 13

— No lecture — Spring break, Day 3

Thu Apr 15

[TBA]

Mon Apr 19

Homework 5 due 8pm

Tue Apr 20

[TBA]

Thu Apr 22

[TBA]

Tue Apr 27

[TBA]

What? Done already?

Thu Apr 29

Paper presentations

Tue May 4

Paper presentations / review / something new

Wed May 5

Drop deadline

Thu May 6

Reading day

Mon May 10

Final exam due 10pm (officially scheduled for 8-11am)