Advanced Topics in Computational Geometry - 236604
Prof. Gill Barequet (
Fall 2005-06


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, 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.