Advanced Topics in Computational Geometry  236604
Prof. Gill Barequet
(barequet@cs.technion.ac.il)
Fall 200506
Syllabus
Random sampling, static and dynamic randomized algorithms, convex hulls,
linear programming, arrangements of line segments and DavenportSchinzel
sequences, Voronoi diagrams with Euclidean and nonEuclidean 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 makeup 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:3012: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,
DavenportSchinzel 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 offline 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, offline and online 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, online and dynamic convex hulls.

(5) Thu 08/12/05, Thu 15/12/05 (Amir Vaxman)
DavenportSchinzel sequences

Complexity of DavenportSchinzel sequences, applications: lower envelopes,
nearestneighbor 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 online Heilbronn's triangle problem in 2D.

(7) Thu 29/12/05 (Alik Zamansky)
Convex hulls in 2 and 3 dimensions

Divideandconquer convex hulls, convex hull of a polyline.

(6.2) Thu 12/01/06 (Osnat Tal)
Packing arguments, II

A lower bound for the online 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, highorder Voronoi diagrams.

(9) Thu 26/01/06, Mon 30/01/06 (Iddo Hanniel)
Voronoi diagrams  NonEuclidean
metric

Power diagrams, affine diagrams, weighted diagrams, L_1 and L_infty.