Computational Geometry, Spring 2022

Instructor: Dan Halperin , [email protected]

Office hours: by appointment; we can have zoom sessions, meet in my office (CheckPoint 434), or correspond by email

Teaching Assistant: Michal Kleinbort, [email protected]

Grader: Tal Levi, [email protected]

---

Although the assignment grades will be used only for improving the final grade, submission of the assignments is mandatory and a prerequisite for taking the exam.

About halfway through the course (probably earlier), we will present a programming assignment.

We encourage you to submit the programming assignment as well. This is not mandatory.

If however you do submit it, then your grade breakdown will be 10% the standard assignments,
15% the programming assignment, and 75% the final exam. Here as well,
the assignments grades will be counted toward the final grade only if they improve it.

The assignments will appear in Moodle; they should be submitted as a pdf file.

1. Assignment no. 1, due: March 14th, 2022.
2. Assignment no. 2, due: April 1st, 2022.
3. Assignment no. 3, due: April 25th, 2022.
4. Programming project, due: June 9th, 2022. Additional information.
5. Assignment no. 4, due: May 23rd, 2022.
6. Assignment no. 5 (optional), due: June 10th, 2022.

---

Course Summary

Below you’ll find a very brief summary of what was covered in class during the semester.
This should not be taken as a complete description of the course’s contents.
For an outline of the course, see for example, the course summary in the Fall 2020-2021 computational geometry course.

---

21.02.22
What is Computational Geometry?
Motivation and techniques. A slow convex hull algorithm. Graham’s O(n log n) algorithm (Chapter 1 in CGAA). (slides1.) Lower bound. Gift-wrapping algorithm for computing the convex hull, Jarvis’s March (Preparata-Shamos, Section 3.3.3).Orientation (Side-of-line) test, course mechanics and overview (slides).

28.02.22
Output sensitive algorithm to compute the intersections of line segments: Bentley Ottmann’s plane sweep (CGAA, Chapter 2), (slides2a).

07.03.22
The Doubly Connected Edge List, DCEL, and map overlay  (CGAA, Chapter 2). (slides2b).Euler’s formula for plane graphs, proof without induction (Proofs from THE BOOK, Aigner-Ziegler, 5th Ed., Chapter 13)The Douglas-Peucker algorithm (see, e.g., wikipedia).

14.03.22
Polygon triangulation and the art gallery problem (slides)

21.03.22
Casting, half-plane intersection, and Linear Programming in low dimensions (CGAA Chapter 4, slides4a).Supplementary material (Slides), up till Unbounded LP.

28.03.22
Unbounded LP2D, LP3D (Slides).Smallest enclosing circle (CGAA Section 4.7, slides4b). GeoGebra files: SEC is unique, SEC new point on boundary

04.04.22
Orthogonal range searching I: kd-trees (CGAA, Chapter 5, slides5a)Orthogonal range searching II: range trees (CGAA, Chapter 5, slides5b).

25.04.22
Orthogonal range searching, continued: fractional cascading, handling degeneracies through composite numbers (CGAA, Chapter 5, slides5b)Introduction to CGAL, guest talk by Efi Fogel (slides)Trapezoidal maps and planar point location (CGAA, Chapter 6, slides6).

02.05.22
Tiling with squares and packing dominos in polynomial time, guest talk by Mikkel Abrahamsen (slides)Trapezoidal maps and planar point location (CGAA, Chapter 6, slides6)Guaranteed logarithmic-time point location (slides, paper).

09.05.22
Point-Line duality, arrangements of lines in the plane, the zone theorem and incremental construction of the arrangement (CGAA, Chapter 8, slides8).More on arrangements and duality (slides).The minimum area triangle problem (CGAL Arrangements and Their Applications, Section 4.2.1).

16.05.22
Voronoi diagrams (CGAA, Chapter 7, slides7_combined)Arcs on the beach line (slides).

23.05.22
Triangulating planar point sets and Delaunay triangulations (CGAA, Chapter 9) (slides)Computing convex hulls in 3D (CGAA, Chapter 11) (slides).

30.05.22
The plan: Connections between major geometric structures (slides)The casting problem revisited (slides) (paper).