Computational Geometry (236719)
Lecturer: Prof. Gill Barequet (barequet@cs.technion.ac.il)
TA: Mr. Tomer Adar (tomer-adar@cs.technion.ac.il)
Fall 2023-24

Syllabus

Fundamental techniques, data structures, and algorithms for solving geometric problems such as computing convex hulls, intersection of line segments, the Voronoi diagram and Delaunay triangulation of a point set, polygon triangulation, range search, linear programming, and point location. Some topics of discrete geometry, e.g., the crossing number of a graph and its applications, are also covered.

Technion Statement

• Academic integrity is essential to an academic community and a fair assessment of your work. All papers submitted in the course must be yours and performed in accordance with the Technion's academic regulations. Do not use chatbots or other manufacturing features that are based on artificial intelligence.
• Writing tools based on artificial intelligence are prohibited at any stage of the work in this course. Using these tools will be considered an unfair academic action and a violation of the Technion's academic fairness policy.

News and Messages

(26/Mar/2024) Exam Term A will be held on Sunday, April 14, 2024. It will be held in Ullmann 805 at time TBA. (Follow this link.)
Allowed material: Any printed or written material (but not shared!).
Forbidden material: All electronic devices (laptops, iPads, phones, etc.).
Not needed: Calculators and similar devices.
Hopefully all of you will pass well Term A, so that there will be no need for Moed B. Please let me know if you do not intend to attend Term A.

(11/Mar/2024) Ex3 is already available in the web page of the course although its formal publication is next week. Enjoy!

(27/Feb/2024) Corrected versions of the helper files for ex4 were uploaded to the web page of the course.

(22/Feb/2024) A visualization of the plane-sweep paradigm (by Abed Naaran), applied to the segment-intersection problem, is available in web page near the .pdf file of the corresponding lecture.

(21/Feb/2024) Ex4 was posted in the web page of the course. Enjoy!
Ex2 is also already available although its formal publication is next week.

(30/Jan/2024) Ex1 was posted in the web page of the course. Enjoy!

(09/Jan/2024) Please note my note of August 2, 2023. Students who do not register to the mailing list unfortunately miss important information that was given in the first 17 E-mail messages that were posted so far.

(09/Jan/2024) Note a change in the lecture hall! Both lectures and recitations will be given in Taub 3.

(02/Aug/2023) All students (including free listeners) are kindly requested to sign up to the mailing list of the course. (This is in addition, and irrelated, to the formal registration to the course! One can leave this mailing list at any time.) For joining the mailing list, please send me your full name, id/student #, faculty, and degree towards which you study. I will post later a link for joining the WhatsApp group of the course.

Bibliography

Main text book: Computational Geometry: Algorithms and Applications (3rd ed.), M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf, Springer-Verlag, 2008.
For background only: Computational Geometry in C (2nd ed.), J. O'Rourke, Cambridge University Press, 1998.

Classes

Classes will be held on Mondays at 10:30-12:30 in Taub 3.
Recitations will be given by Mr. Tomer Adar in Taub 3, immediately after the lectures (i.e., on Mondays at 12:30-13:30).
In case the audience includes non-Hebrew speakers, the lectures and recitations will be given in English.

Grading Policy

3 Home assignments (dry): ~12.5% (compulsory, submission in singletons!!);
Running project (wet): ~12.5% (same);
Final exam: 75% (1st term: Tuesday 6/Feb/2024, at ??:??, hall ???; 2nd term: hopefully will not be needed).

Assignment 1 (dry): published 30/Jan/2024, due 13/Feb/2024

Assignment 2 (dry): published 26/Feb/2023, due 11/Mar/2023

Assignment 3 (dry): published 18/Mar/2024, due 01/Apr/2024

Assignment 4 (wet): published 21/Feb/2024, due 04/Apr/2023 (Utility modules: C, Python)

Course summary and slides

(1) Introduction
What is Computational Geometry? Example problems and motivations. Naive, incremental, and divide-and-conquer convex-hull algorithms.
(2) Vectors, Plane sweep
Vector cross product and orientation test. Segment-intersection test. Convex-polygon queries. Plane-sweep paradigm. Segment-intersection algorithm.
A visualization of the algorithm, by Abed Naaran, is available here.
(3) Polygon triangulation
The art-gallery theorem. Partitioning a simple polygon into monotone pieces. Triangulating a monotone polygon.
(4) Linear programming
What is linear programming. A D&C algorithm for half-planes intersection. An incremental algorithm for half-planes intersection. Randomized linear programming. Unbounded linear programming. Smallest enclosing disk of a 2D point set.
(5) Orthogonal range searching
1D range searching. 2D kd-trees. 2D Range trees.
(6) Point location
Slabs structure. Trapezoidal map. A randomized incremental algorithm for computing a trapezoidal map. Worst- and average-case Time/Space analysis of the algorithm. Handling degeneracies.
(7) Voronoi diagram
Definition and variants. A plane-sweep algorithm for computing the Voronoi diagram of a point set.
(8) Duality
A point-line duality in the plane and its properties.
(9) Line Arrangements
Line arrangements and their properties. The zone theorem. Computing an arrangement of lines. Levels in line arrangements. Halfspace discrepancy and its dual problem.
(10) Delaunay triangulation
Triangulation of a point set. Angle vector and the triangulation that maximizes it. Delaunay triangulation and its relation to the angle vector. A randomized incremental algorithm for computing the Delaunay triangulation.
(11) The crossing-number lemma
The crossing-number lemma and a few applications of it.
(12) 2-point site Voronoi diagrams
Some 2-point site distance functions and their respective Voronoi diagrams.
(13) A few theorems
The upper-bound theorem. Interpretations of Voronoi diagrams. Zone theorems. Envelopes of lines and planes.
(0) Administration
(a) Planar graphs
Graph definition, planar graphs, Euler's formula, the DCEL structure.
(b) Sweepline
The sweep-line paradigm.
(c) Polygonal skeletons
Straight skeleton of a polygon and a polyhedron. Their complexities, and algorithms to compute them.
(d) Fractional cascading
Fractional cascading for range searching.
(e) Casting
Polyhedron casting.
(f) Point location
Efficient data structures for point location.
(g) Voronoi diagram
More and alternative definitions. Lloyd's algorithm.
(h) Duality
Geometric point-line duality.
(i) Space Partitioning
BSP trees, quadtress.
(j) Triangulations
Triangulations.
(k) Date Structures
Some sophisticated data structures.
(l) More Date Structures
Some more sophisticated data structures.