Computer Science 279/479

Computational Geometry

Fall 2024

Textbooks:

A textbook is not required for this course. Homework problem statements will be self contained. It is a good idea to have access to the recommended books (electronic or paper; the version/edition is not too important) while taking the course and after.

[M21] = Computational Geometry, D. Mount, 2021.
[PS85] = Computational Geometry (An Introduction), F. P. Preparata, M.I. Shamos, 1985.
[BKO08] = Computational Geometry (Algorithms an Applications) (3rd ed), M. de Berg, M. van Kreveld, M. Overmars, 2008.
[O98] = Computational Geometry in C (2nd ed), J. O'Rourke, 1998.
[M94] = Computational Geometry (An Introduction Through Randomized Algorithms), K. Mulmuley, 1994.

Prerequisites: CSC172.

Schedule

Aug. 26 Mon - Introduction (points, lines, segments, convexity, planarity) (reading: [M21] chapters 1 and 21, [BKO08] chapter 1).
Aug. 28 Wed - Convex Hulls I (reading: [M21] chapter 2).

Sep. 2 Mon - no class (Labor Day).
Sep. 4 Wed - Convex Hulls II (reading: [M21] chapter 3).

Sep. 9 Mon - Art Gallery Problem (reading [M21] chapter 27, [BKO08] chapter 3.1).
Sep. 11 Wed - Sweep Algorithms (line segment intersection) (reading: [M21] chapter 4, [BKO08] chapter 2). Homework #1 due (submit on gradescope).

Sep. 16 Mon - no class
Sep. 18 Wed - no class

Sep. 23 Mon - Polygon Triangulation (reading: [M21] chapter 5, [BKO08] chapter 3.3).
Sep. 25 Wed - Halfplane Intersection (reading: [M21] chapter 6), [BKO08] chapters 4.1 and 4.2). Homework #2 due (submit on gradescope).

Sep. 30 Mon - Linear Programming in Low dimensions I (reading: [M21] chapter 7, [BKO08] chapters 4.3, 4.4).
Oct. 2 Wed - Linear Programming in Low dimensions II (reading [M21] chapter 23).

Oct. 7 Mon - Point Location I (reading: [M21] chapter 8, [BKO08] chapter 5).
Oct. 9 Wed - Point Location II (reading: [M21] chapter 9, [BKO08] chapter 6). Homework #3 due (submit on gradescope).

Oct. 14 Mon - FALL BREAK.
Oct. 16 Wed - Closest Pair of Points.

Oct. 21 Mon - Voronoi Diagrams (reading: [M21] chapter 10, [BKO08] chapter 7).
Oct. 23 Wed - Delaunay Triangulations I (reading: [M21] chapter 11, [BKO08] chapter 9). Homework #4 due (submit on gradescope).

Oct. 28 Mon - Delaunay Triangulations II (reading: [M21] chapter 12).
Oct. 30 Wed - k-d Trees (reading: [M21] chapter 14).

Nov. 4 Mon - Orthogonal Range Trees (reading [M21] chapter 15).
Nov. 6 Wed - Lower Bounds, Algebraic decision trees (reading: [PS85] chapter 1) Homework #5 due (submit on gradescope).

Nov. 11 Mon - Segment trees (reading: [BKO08] chapter 10).
Nov. 13 Wed - Coresets (reading: [M21] chapter 18).

Fun Topics

Nov. 18 Mon - Quantifier Elimination I.
Nov. 20 Wed - Quantifier Elimination II. Homework #6 due (submit on gradescope).

Nov. 25 Mon - Quantifier Elimination III.
Nov. 27 Wed - THANKSGIVING (no class).

Dec. 2 Mon - (Low Dimensional) Computational Topology I.
Dec. 4 Wed - (Low Dimensional) Computational Topology II.

Dec. 9 Mon - (Low Dimensional) Computational Topology III.

Grading

The grade for the course is computed from the homework grade. There will be 6 homework sets, see the schedule above for the due dates. Each homework set is 4-6 problems, mostly theoretical (there will be a few implementation problems).

Homework Rules

Homework will be submitted on Gradescope, the deadline is 11:59pm on the date the homework is due.
Homework must be typeset (for example, you can use LaTeX, word, powerpoint (of course, any open office or google variants are fine), etc).
No late homework will be accepted without instructor's permission (a permission must be requested at least 24 hours before the due date).
You may work with other people on the homework, but you must each write up your solutions separately without any written aid. If you work with other people, indicate who you worked with on your solution.

This course follows The University Policy on Academic Honesty.