Advanced Topics in Computational Geometry - 236604
Prof. Gill Barequet
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
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.
Reminder: The lecture of Thursday, January 5, 2006, is canceled.
Tomorrow, Thursday 22/12, we will meet for the second hour of the lecture,
that is, 11:30-12:30.
Note that there will NOT be a lecture in Thursday 05/01/06.
Note that there will NOT be a lecture in Thursday 10/11/05.
Main text book:
J.-D. Boissonnat and M. Yvinec,
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.
Class performance (talk) and class attendance (3 absences allowed): 70%.
Final quiz: 30% (February 13, 2006, 13:00, Taub 5).
(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)
Basic concepts, the sampling theorem, the moment theorem.
(3) Thu 24/11/05, Thu 01/12/05 (Michal Aharon)
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)
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
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
Power diagrams, affine diagrams, weighted diagrams, L_1 and L_infty.