Lecture: Monday, 16:00-19:00, Melamed Auditorium 006
Grader: Tom Tsabar, [email protected]
Maibox no. (TBD), Schriebr, 1st floor
The course covers fundamental algorithms for solving geometric problems such as computing convex hulls, intersection of line segments, Voronoi diagrams, polygon triangulation, and linear programming in low dimensional space. We will also discuss several applications of geometric algorithms to solving problems in robotics, GIS (geographic information systems), computer graphics, and more.
Bibliography
The main textbook of the course is:
- Computational Geometry: Algorithms and Applications (CGAA), 3rd edition by M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf.
A bibliographic list for the course
Slides
I will often use slides that accompany the main textbook of the course.The slides are by Marc van Kreveld and they can be found at the following site: Geometric Algorithms
Assignments, Examination and Grade
The standard assignments will account for 10% of the final grade, in case they improve the final grade.
The grade in the final exam will account for the remaining 90% of the grade in the course.
Exam(ple) [pdf]
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.
This year’s programming assignment is Optimal Area Polygonalization as described in the Geometric Optimization Challenge 2019. We will use the same input and output format. More details on the assignment will be provided later.
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 here.
- Assignment no. 1 file , due: March 25th, 2019
- Assignment no. 2 file , due: April 8th, 2019
- Programming assignment (pdf file), due: June 2nd, 2019, 23:59; see additional information
- Assignment no. 3 file , due: May 1st, 2019
- Assignment no. 4 file , due: May 20th, 2019
- Assignment no. 5 file , due: June 24th, 2019
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.
- 04.03.19
- What is Computational Geometry?
Course outline, motivation and techniques. A slow convex hull algorithm. Orientation (Side-of-line) test. Graham’s O(n log n) algorithm (Chapter 1 in CGAA). (Slides 1.) Lower bound. Gift-wrapping algorithm for computing the convex hull, Jarvis’s March (Preparata-Shamos, Section 3.3.3) - 11.03.19
- Output sensitive algorithm to compute the intersections of line segments: Bentley Ottmann’s plane sweep; handling degeneracies. The Doubly Connected Edge List, DCEL (CGAA, Chapter 2). (Slides 2a, and part of Slides 2b.)
- 18.03.19
- Point-Line duality, arrangements of lines in the plane, the zone theorem and incremental construction of the arrangement (CGAA, Chapter 8). Applying all this to solve collinearity, and to sum of squares of face complexities.
- 25.03.19
- Map overlay and applications (CGAA, Chapter 2).
- Polygon triangulation and art gallery problems – Part I: combinatorial bounds and properties (O’Rourke’s book, CG in C, Chapters 1 and 2, and in CGAA, Chapter 3). Part II: Triangulating a monotone polygon (CGAA, Chapter 3) and TO BE CEOMPLETED NEXT WEEK decomposing a polygon into monotone polygons via trapezoidal decomposition (O’Rourke’s book, Chapter 2).
- 01.04.19
- We have shown that \Omega(n^{3/2} guards are sometimes needed to guard a polyhedron with n vertices. The construction is due to Seidel and its presentation is taken from the book Art Gallery Theorems and Algorithms by J. O’Rourke.
- The casting problem. Half plane intersection. Introduction to Linear Programming (CGAA, Chapter 4). (Slides 4a)
Linear programming in 2D continued: the unbounded case; linear programming in 3D. (CGAA, Chapter 4).Linear-time solution to the casting problem (paper)
- 29.04.19
- Orthogonal range searching: kd-trees, range trees, handling degeneracies through composite numbers (CGAA, Chapter 5)
- The Douglas-Peucker algorithm for line simplification.
- 06.05.19
- Trapezoidal maps and planar point location (CGAA, Chapter 6).
13.05.19:
Voronoi diagrams of points in the plane: structure, complexity, and Fortune’s algorithm (CGAA, Chapter 7).20.05.19
Guaranteed logarithmic point location, Nearest-neighbor search using kd-trees, and Nearest-neighbor search in motion planning [PL paper], [slides]27.05.19Voronoi diagrams, review.Legal triangulations and Delaunay triangulations (CGAA, Chapter 9, Sections 9.1,9.2). [Slides, up to #33]03.06.19The largest disc in a convex polygon. Section 2.6 in Understanding and using linear programming, Matoušek and Gärtner.The lifting transform. The connection between convex hulls, envelopes, intersection of half-spaces, Voronoi diagrams and Delaunay triangualtions (partly covered in CGAA, Sections 11.4 and 11.5).10.06.19The minimum enclosing disk problem (CGAA, Chapter 4; Slides 4b).Randomized construction of the convex hull of points in 3D (CGAA, Sections 11.2 and 11.3, without the proof of Lemma 11.6).