Advanced Topics in Computational Geometry - 236601 (temporary number)
Dr. Gill Barequet (barequet@cs.technion.ac.il)
Spring 2002-3

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

(29/04/03)
Note the irregular schedule of meetings till the end of the semester. Many Thursday meetings are canceled; instead we'll have Sunday meetings. Sunday 4/5 is Yom Matkonet as Thursday, and there will be compensation meetings on Sundays 11/5 (9:30, T-8) and Sunday 1/6 (9:30, T-8).

(07/04/03)
Note that next Monday 14/4 is Yom Matkonet as Thursday.

(03/04/03)
Note that the lecture titles are now links to on-line material. Lecturers are requested to provide .ps files after their talks.

(24/03/03)
Eyal A. found the numerical error. It was a factor-2 error in the computation of the volume of the forbidden slab: it is 6c/(n^{10/3}|T_{ijk}|) and not 12c/(n^{10/3}|T_{ijk}|).

(14/03/03)
The material of the first lecture can be found here. (There is a tiny numerical error in P. 3; who will find it first?)

(13/03/03)
The class of Thursday 20/3 is canceled.

(12/03/03)
As in the regular Computational-Geometry course, please register to this course's mailing list (you should know how by now).

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% (1st term: Sunday 29/06/03 at 1pm, Ulman 606: exam, solution; no 2nd term).

Course Summary

(1) Thu 06/03/03 (Gill B.)       Nested Packing Arguments

Lower bounds for the on-line Heilbronn's triangle problem in 2D and 3D.

(2) Thu 13/03/03, Thu 27/03/03 (Aya Levi-Steiner)       Random Sampling

Basic concepts, the sampling theorem, the moment theorem.

(3) Thu 27/03/03, Thu 03/04/03 (Yuval Scharf)       Randomized algorithms

Conflict and influence graphs, off-line and on-line algorithms, example: trapezoidal map of line segments.

(4) Thu 03/04/03, Thu 10/04/03 (Oded Fuhrmann)       Dynamic randomized algorithms

Insertions and deletions, combination of conflict and influence graphs, example: trapezoidal map of line segments.

(5) Mon 14/04/03, Thu 01/05/03 (Avishay Sidlesky)       Incremental convex hulls

A deterministic algorithm, on-line and dynamic convex hulls.

(6) Thu 01/05/03 (Gill B.)       The probabilistic method

A lower bound for the off-line Heilbronn's triangle problem in 2D.

(7) Sun 04/05/03 (Osnat Tal)       Convex hulls in 2 and 3 dimensions

Divide-and-conquer convex hulls, convex hull of a polyline.

(8) Sun 11/05/03, Thu 15/05/03 (Alex Bogomjakov)       Linear programming

Randomized linear programming, convex hulls using a shelling.

(9) Thu 15/05/03 (Gill B.)       The d-D moment curve

A lower bound for the off-line Heilbronn's triangle problem in d-D (d > 2).

(10) Thu 22/05/03 (Eyal Ackerman)       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.

(11) Sun 01/06/03 (Zvi Devir)       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.

(12) Thu 12/06/03, Wed 19/06/03 (Aya Levi-Steiner)       Voronoi diagrams - Non-Euclidean metric

...