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.
(22/05/03)
Please note that next week we do NOT meet on Thursday 29/5, and in the
following week we meet (irregularly) on Sunday 1/6 but then again do not
meet on Thursday 5/6 due to Shavu'ot.
(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).
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.
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).