Advanced Topics in Computational Geometry - 236604
Prof. Gill Barequet
(barequet@cs.technion.ac.il)
Fall 2005-06
Syllabus
Random sampling, static and dynamic randomized algorithms, convex hulls,
linear programming, arrangements of line segments and Davenport-Schinzel
sequences, Voronoi diagrams with Euclidean and non-Euclidean metrics,
probabilistic proofs, and variants of Heilbronn's triangle problem.
News and Messages
(19/01/05)
The lecture of Thursday, February 2, 2006, is canceled.
A make-up lecture will be given in Monday, January 30, at 13:30, in Taub 7.
(31/12/05)
Reminder: The lecture of Thursday, January 5, 2006, is canceled.
(21/12/05)
Tomorrow, Thursday 22/12, we will meet for the second hour of the lecture,
that is, 11:30-12:30.
(11/11/05)
Note that there will NOT be a lecture in Thursday 05/01/06.
(27/10/05)
Note that there will NOT be a lecture in Thursday 10/11/05.
Bibliography
Main text book:
J.-D. Boissonnat and M. Yvinec,
Algorithmic Geometry,
Cambridge University Press, UK, 1998.
A focus on D.S. sequences:
M. Sharir and P.K. Agarwal,
Davenport-Schinzel Sequences and Their Geometric Applications,
Cambridge University Press, 1995.
Grading Policy
Class performance (talk) and class attendance (3 absences allowed): 70%.
Final quiz: 30% (February 13, 2006, 13:00, Taub 5).
Course Summary
-
(1) Thu 03/11/05 (Gill B.)
The probabilistic method
-
A lower bound for the off-line Heilbronn's triangle problem in 2D.
-
(2) Thu 17/11/05 (Osnat Tal)
Random Sampling
-
Basic concepts, the sampling theorem, the moment theorem.
-
(3) Thu 24/11/05, Thu 01/12/05 (Michal Aharon)
Randomized algorithms
-
Conflict and influence graphs, off-line and on-line algorithms,
example: trapezoidal map of line segments.
-
(4) Thu 01/12/05, Thu 08/12/05, Thu 15/12/05 (Gadi Aleksandrowicz)
Incremental convex hulls
-
A deterministic algorithm, on-line and dynamic convex hulls.
-
(5) Thu 08/12/05, Thu 15/12/05 (Amir Vaxman)
Davenport-Schinzel sequences
-
Complexity of Davenport-Schinzel sequences, applications: lower envelopes,
nearest-neighbor among moving points, a cell in an arrangement of line
segments, geometric graphs.
-
(6.1) Thu 22/12/05 (Gill B.)
Packing arguments, I
-
A lower bound for the on-line Heilbronn's triangle problem in 2D.
-
(7) Thu 29/12/05 (Alik Zamansky)
Convex hulls in 2 and 3 dimensions
-
Divide-and-conquer convex hulls, convex hull of a polyline.
-
(6.2) Thu 12/01/06 (Osnat Tal)
Packing arguments, II
-
A lower bound for the on-line Heilbronn's triangle problem in 3D and 4D.
-
(8) Thu 12/01/06, Thu 19/01/06 (Alina Shaikhet)
Voronoi diagrams - Euclidean
metric
-
Power of points w.r.t. spheres, the paraboloid in one higher dimension and
the Voronoi diagram, Delaunay complexes, high-order Voronoi diagrams.
-
(9) Thu 26/01/06, Mon 30/01/06 (Iddo Hanniel)
Voronoi diagrams - Non-Euclidean
metric
-
Power diagrams, affine diagrams, weighted diagrams, L_1 and L_infty.