Computational Geometry (236719)
Lecturer: Prof. Gill Barequet
TA: Mr. Gil Ben-Shachar
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.
News and Messages
Ex3 was posted in the web page of the course. Enjoy!
In the wake of Hanukkah, there is no class today.
Ex2 was posted in the web page of the course. Enjoy!
Ex1 was posted in the web page of the course. Enjoy!
Ex4 was posted in the web page of the course. Enjoy!
Students who did not fulfill my request from September 16, 2020, are
humbly asked to do it today. (Otherwise they will not get the
password for the zoom meetings...)
All students (including free listeners) are kindly requested to join
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 e-mail me your full name, id/student #,
faculty, and degree toward which you study.
As much as I will be happy to hold in-person lectures, we will start the
semester with on-line lectures. If possible, we will switch later to
in-person lectures. Zoom meetings:
Lectures: https://technion.zoom.us/j/518018934?pwd=??? (password
sent by email)
Recitations: https://technion.zoom.us/j/91964945349 (no password)
Passwords will be given only to students and non-students registered to
the mailing-list of the course, see above under "News and Messages."
3 Home assignments (dry): ~12.5% (compulsory, submission in
Running project (wet): ~12.5% (same);
Final exam: 75% (1st term: Thursday 04/Feb/21, at ??:??, hall ???;
2nd term: hopefully will not be needed).
If a physical exam is not possible, an on-line exam will
Assignment 1 (dry):
published 16/Nov/20, due 30/Nov/20
Assignment 2 (dry):
published 01/Dec/20, due 21/Dec/20
Assignment 3 (dry):
published 04/Jan/21, due 18/Jan/21
Assignment 4 (wet):
published 02/Nov/20, due 24/Dec/20 (before ex3!)
Course summary and slides
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.
(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.
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.
(a) Planar graphs
Graph definition, planar graphs, Euler's formula, the DCEL structure.
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.
(f) Point location
Efficient data structures for point location.
(g) Voronoi diagram
More and alternative definitions. Lloyd's algorithm.
Geometric point-line duality.
(i) Space Partitioning
BSP trees, quadtress.
(k) Date Structures
Some sophisticated data structures.
(l) More Date Structures
Some more sophisticated data structures.