CS 763: Computational Geometry, Fall 2016


Anna Lubiw, David R. Cheriton School of Computer Science, University of Waterloo
alubiw@uwaterloo.ca, DC 2334, (519) 888-4567, ext. 34449

Contents: Organization, Course Outline, Assignments, Resources, Lectures, Project, Presentation Schedule



Time and Place: Tuesday and Thursday, 1:00 -- 2:20 pm. DC 2568.



Assignments will be marked based on correctness but also on quality of explanations: strive for clarity and precision. Assignments are due Tuesdays in class.
Assignment 1 [pdf] Tuesday Sept. 27
Assignment 2 [pdf] Tuesday Oct. 4
Assignment 3 [pdf] Tuesday Oct. 18
Assignment 4 [pdf] Tuesday Oct. 25
Assignment 5 [pdf] Tuesday Nov. 8
Assignment 6 [pdf] Tuesday Nov. 22

Course Outline


Background: I will assume a background in algorithms and data structures equivalent to a decent undergraduate course (e.g. UW's CS 341).


Web Pages

Finding Papers


L01 Tu Sep 13 slides Every polygon can be triangulated. The Art Gallery Theorem. [CG] 3.1. [CGinC] 1.1, 1.2. [D&CG] 1.1 - 1.3.
L02 Th Sep 15 slides O(n log n) time triangulation algorithm via trapezoidization. [CG] 3.2, 3.3 (slightly different algorithm). [CGinC] 2.1 - 2.4.
Also the idea of randomized trapezoidization. [CGinC] 7.11.4. [CG] 6.2. Seidel's paper
L03 Tu Sep 20 slides Partitioning polygonal regions and polyhedra. [CGinC] 2.5. Chazelle's paper Bern and Eppstein
L04 Th Sep 22 slides Convex Hull in the Plane [CGinC] 3. [CG] 1.1. Chan's paper
L05 Tu Sep 27 slides Convex Hull in Dimension d [CGinC] 4. [CG] 11.
L06 Th Sep 29 slides More on Convex Hull - randomized incremental algorithm [CGinC] 4. [CG] 11. Seidel's paper
L07 Tu Oct 4 slides Linear Programming [CG] 4. Understanding and Using Linear Programming a short basic book on linear programming
L08 Th Oct 6 slides Voronoi diagrams and Delaunay triangulations [CGinC] ch. 5.[CG] ch. 7, 9. [D&CG] ch. 4.
L09 Th Oct 13 slides Voronoi diagrams and Delaunay triangulations, continued same as above
L10 Tu Oct 18 slides Delaunay triangulations, continued same as above. Better presentation of incremental algorithm.
L11 Th Oct 20 slides Triangulations refs. in slides. Also Bern-Eppstein survey
L12 Tu Oct 25 slides Triangulations, continued refs. in slides.
L13 Th Oct 27 slides Line Arrangements [CGinC] ch. 6. [CG] ch. 8.
L14 Tu Nov 1 slides Planar Point Location [CGinC] section 7.10 and 7.11. [CG] ch. 6 and section 10.3.
L15 Th Nov 3 slides Shortest Paths [CGinC] section 8.2. [CG] chapter 15.
L16 Th Nov 10 Range Searching (Timothy Chan) [CG] chapter 5.
L17 Tu Nov 15 slides Motion Planning [CGinC] chapter 8. [CG] chapter 13.
L18 Th Nov 17 see L17 Motion Planning, continued. Plus student presentations.
L19 Tu Nov 22 student presentations
L20 Th Nov 24 student presentations
L21 Tu Nov 29 student presentations
L22 Th Dec 1 student presentations
L19 Tu Nov 22 student presentations

Presentation Schedule

Thursday November 17: Simon, Jumyung
Tuesday November 22: Zachary, Sean, Brandon, William
Thursday November 24: Armin, Jeremy, Ellen, Alexei
Tuesday November 29: Sebastian, Kshitij, Kewei, Pak Hay
Thursday December 1: Jade, Shayan, Yuan, Corey