COMP 163: Computational Geometry
Class notes and links are found on the Reading page.
Fall 2017 lectures:
Lecture 7: Wednesday, Sep. 27: The segment intersection problem. Point location. Possibly some distance problems.
Lecture 6: Monday, Sep. 25: Two fancy convex hull algorithms
Lecture 5, Sep. 20 (codename: chocolate-surprise 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).
[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]
Total time spent so far: 580 minutes = 9h40m = close to 8 normal lectures
Fall 2016 lectures:
- Coming up: More data depth, and some of section 17
- Lecture 21. Thursday, Dec. 1: Data depth (section 18.1, and first 5 pages of 18.2.1)
- Lecture 20. Tuesday, Nov. 29: Lemonade LP, Borsuk-Ulam, and ham sandwich cuts (sections 15 and 16.1-3)
- Lecture 19. Thursday, Nov. 17: Duality
- Lecture 18. Tuesday, Nov. 15: high-dimensional range counting (section 12)
- Lecture 17. Thursday, Nov. 10: segment intersection, interval and box overlaps, and review of 1D range counting (section 13)
- Exam 1. Thursday, Nov. 3
- Lecture 16. Tuesday, Nov. 1: discussed homework 2
- Lecture 15. Thursday, Oct. 27: ended Voronoi, continued with proximity graphs (section 11)
- Lecture 14. Tuesday, Oct. 25: discussed homework 1
- Lecture 13. Thursday, Oct. 20: more Voronoi: focused on time complexity (check all section 10)
- Lecture 12. Tuesday, Oct. 18: started Voronoi diagrams (section 10, only first pdf of notes)
- Lecture 11. Thursday, Oct. 13: discussed projects
- Lecture 10. Tuesday, Oct. 11: point location (section 9) --- [end of Exam 1 topics]
- Lecture 9. Thursday, Oct. 6: the two advanced algorithms for convex hull of a point set (section 5.7)
- Lecture 8. Tuesday, Oct. 4: star-shaped polygons, finding the kernel and triangulating (section 7)
- Lecture 7. Tuesday, Sept. 27: convex hull of polygon (section 6)
- Lecture 6. Thursday, Sept. 22: decomposing polygons into convex pieces (section 3), and computing the visibility region of a point (section 7, before computing kernel of a star).
- Lecture 5. Tuesday, Sept. 20: the art gallery problem (section 3)
- Lecture 4. Thursday, Sept. 15: Decomposing simple polygons into monotone pieces (section 4.1, after the "testing monotonicity" part, and also 4.2). We won't cover 4.3. Also, triangulation of point sets, and Euler's formula (section 3.1, before "art gallery")
- Lecture 3. Tuesday, Sept. 13: Triangulating polygons, ear-finding, balanced diagonals (rest of section 2). Triangulating monotone polygons (section 4.1, before the testing monotonicity part)
- Lecture 2. Thursday, Sept. 8: Convex hull of point set (Section 5: pdf (a) and (b), all subsections up to 5.6). Finding diagonals in polygons (Section 2.1, before triangulating polygons)
- Lecture 1. Tuesday, Sept. 6: Intro and basics. Plumb-line algorithm. Winding number algorithm. Area of polygon. Browse Section 1.
What was covered in the Fall 2015 semester:
- Lecture 22. Tuesday, Dec.8: Separating point sets (dual of LP). The Borsuk-Ulam theorem, and ham sandwich cuts (sections 14 and 16).
- Lecture 21. Thursday, Dec.3: Sweepline algorithms (segment intersection and rectangle overlap). Plus a little bit of duality. Section 13. Section 14 (up to page 6; will resume from page 12).
- Lecture 20. Tuesday, Dec.1: Range counting. Section 12.
- Lecture 19. Tuesday, Nov.24: The last of Delaunay and Vornoi: existence of O(nlogn) algorithm, other metrics, furthest-point diagram, etc. Proximity graphs. See rest of section 10, and section 11 (not necessarily 11.2 or 11.4).
- Lecture 18. Thursday, Nov.19: Delaunay triangulations.
Section 10.1 (rest of 2nd pdf). Also 10.7, 10.8
- Lecture 17. Tuesday, Nov.17: More Voronoi diagrams.
Section 10.1 (rest of 1st pdf, and first 4 pages of 2nd pdf). Also 10.7, 10.8
- Lecture 16. Thursday, Nov.12: Midterm recap, and intro to Voronoi diagrams.
Section 10.1 (first 9 slides of first pdf).
- Lecture 15. Thursday, Nov.5: Point location. Section 9.
- Lecture 14. Thursday, Oct.29: The two O(nlogh) convex hull algorithms for point sets.
Section 5.7. See 5.6 on merge-hull as well. See 5.1 for class notes.
- Lecture 13. Tuesday, Oct.27: Went over triangulating stars without kernel knowledge again, talked about projects and some of my research.
- Lecture 12. Thursday, Oct.22: Linear programming (including algorithm for 2D).
- Lecture 11. Tuesday, Oct. 20: constructing a visibility polygon, finding kernels, and triangulating star-shaped polygons in linear time.
See Section 7 (in particular 7.1, 7.2, 7.3, 7.4.1, 7.5). Lots of project opportunities here.
- Oct. 13: cancelled. Oct. 15: midterm
- Lecture 10. Thursday, Oct.8: Decomposing polygons into monotone parts.
Section 4.1 (from page 91). Section 4.2
- Lecture 9. Tuesday, Oct.6: Decomposing polygons into convex parts. Triangulating monotone polygons.
Section 3.1 (from page 64), and 3.4. Section 4.1 (up to page 42).
- Lecture 8. Thursday, Oct.1: The art gallery problem. Section 3.1, until page 63. Also 3.2 and 3.3.
- Lecture 7. Tuesday, Sept. 29: "Balanced" diagonals in polygons (section 2.5). Triangulating point sets (section 3.1, the first 21 pages). Also talked about polygonizing point sets, on the blackboard.
- Lecture 6. Thursday, Sept. 24: Polygon triangulation, finding ears. Rest of section 2.1. Also check out 2.2.
- Lecture 5. Tuesday, Sept. 22: Finding diagonals. Section 2.1, first 6 pages of the pdf.
- Lecture 4. Thursday, Sept. 17: Melkman's algorithm (section 6). Incremental convex hull for points.
- Lecture 3. Tuesday, Sept. 15: Sklansky scan, WEV polygons, Quickhull, discussed lower bound for convex hull of points.
See Sections 5.5 and 6.1 (excluding Melkman's algorithm)
- Lecture 2. Thursday, Sept. 10: Convex hull for points: Jarvis march (aka gift-wrapping), Graham scan. See first PDF in Section 5.1. Also, 5.3 and 5.4.
- Lecture 1. Tuesday, Sept. 8: Intro and basics. Jordan curve theorem. Simple convex hull algorithms. Plumb-line algorithm. Winding number algorithm. Area of polygon. Browse Section 1.