COMP 163: Computational Geometry
Class notes and links are found on the Reading page.
Fall 2017 inclass lectures:
Total time spent in class: 1600 minutes ~ 26.6 hours ~ roughly 21.3 normal lectures
(not counting videos, exam and review)

Lecture 16: Dec. 6. (codename: gingerbread)
Combinatorial geometry: Helly, Radon, Tverberg, Caratheodory, ErdosSzekeres, Horton. Depth centerpoints.
Reading: sections 17 and 18.4
[we spent 1h50min on this lecture]

Lecture 15: Dec. 4. (codename: caramelfilled chocolate)
Computation of 2D medians
Reading: section 18.2 and 18.3
[we spent 75min on this lecture]

Lecture 14: Nov. 29 (codename: chocolate chip)
Proximity graphs, and data depth (up to computation of various depths but not computation of medians)
Reading: section 11, then section 18.1 and half of 18.2
[we spent 1h50min on this lecture]

Lecture 13: Nov. 20, guest lecture by Hugo Akitaya
Hamsandwich cuts, BorsukUlam theorem
Reading: section 16
[we spent 75 minutes (at least?) on this lecture]

Lecture 12: Nov. 15, guest lecture by Hugo Akitaya
Voronoi game (competitive areagrabbing), FPVD in O(nlogh), more about Delaunay and 3D convex hull.
Reading: finish everything in section 10.
[we spent 1.5 hrs (at least?) on this lecture]

Lecture 11: Nov. 13, guest lecture by Diane Souvaine
Largest empty circle, definition of medial axis and Furthest Point Voronoi, mention of Delaunay vs 3D convex hull. Least median of squares regression. Topological sweep.
Reading: Diane's handouts, and more of section 10. I do not have course notes on regression or topological sweep.
[we spent two hours on this lecture]

Lecture 10: Nov. 6, guest lecture by Diane Souvaine
Duality
Reading: Diane's handouts and section 14.
[we spent 1:15 on this lecture]

Lecture 9: Nov. 1, guest lecture by Diane Souvaine
Voronoi diagrams 2
Reading: Diane's handouts, and section 10.
[we spent 1:15 on this lecture]

Lecture 8: Oct. 30, guest lecture by Diane Souvaine
Voronoi diagrams 1
Reading: see above
[we spent 1:40 on this lecture]

Lecture 7: Sep. 27 (codename: klondike)
Rotating calipers. Segment intersection. Point location.
Reading: sections 8, 9 and 13 (except overlapping intervals and rectangles)
[we spent 1:50 on this lecture]

Lecture 6, Sep. 25 (codename: oreo & rum ball onetwo punch)
Two fancy convex hull algorithms
Reading: 5.1 (third and fourth pdf), and 5.7, 5.8, 5.9
[we spent 1:15 on this lecture]

Lecture 5, Sep. 20 (codename: chocolatesurprise croissant)
Visibility of point in polygon. Finding kernels, triangulating stars, decomposing a polygon into monotone pieces.
Reading: End of 4.1 (not testing monotonicity), 4.2, and section 7.
[we spent 2:00 on this lecture]

Lecture 4, Sep. 15 (codename: Tiramisu)
Guarding from only convex or only reflex vertices. Decomposing a polygon into convex pieces. A discussion of a research problem involving ``guards" and ``witnesses" (aka rock bands). Triangulating a monotone polygon.
Reading: The rest of section 3. Also section 4.1, first 42 slides.
[we spent 1:35 on this lecture]

Lecture 3, Sep. 13 (codename: flavorless waffle cookie)
More about convex hull of point set, then convex hull of polygon, triangulation of point set, and the art gallery problem.
Reading: section 5.6 (also see second pdf in 5.1). Section 3 (first 60 slides; nothing about convex decomposition yet).
Section 6.
[we spent 2:25 on this lecture]

Lecture 2, Sep. 11 (codename: macaroon)
More about finding diagonals, triangulating polygons, convex hull of a point set.
Reading: section 2, and section 5.3, 5.4, 5.5 (also see first pdf in 5.1)
[we spent 1:55 on this lecture]

Lecture 1, Sep. 8 (codename: geometry feast)
The basics, and finding a chord.
Reading: section 1.
[we spent 1:45 on this lecture]