Discrete Algorithmic Geometry - 236739
Prof. Gill Barequet (barequet@cs.technion.ac.il)
Fall 2007-08


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, polyomino counting, and variants of Heilbronn's triangle problem.

News and Messages

Note that the meeting of Thursday, February 14, is canceled.


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% (TBA).

Course Summary

(1) Mon 21/01/08 (Gill B.)       Introduction; Heilbronn's triangle problem
A lower bound for the on-line Heilbronn's triangle problem in 2D.
Source: W.M. Schmidt, On a problem of Heilbronn, J. London Mathematical Society (2), 4 (1971), 545-550.

(2) Mon 21/01/08, Thu 07/02/08 (Gadi A.)       The probabilistic method
Basic examples, a lower bound for the off-line Heilbronn's triangle problem in 2D.
Source: N. Alon and J.H. Spencer, The Probabilistic Method, John Wiley & Sons, 1992.

(3) Thu 21/02/08 (Hanna M.)       Random Sampling
Basic concepts, the sampling theorem, the moment theorem.

(4) Thu 06/03/08 (Hanna M.)       Randomized algorithms
Conflict and influence graphs, off-line and on-line algorithms, example: trapezoidal map of line segments.

(5) Thu 06/03/08 (Gill B.)       Transfer-matrix algorithms
Counting polyominoes in 2D.
Source: I. Jensen, Enumerations of lattice animals and trees, J. of Statistical Physics, 102 (2001), 865-881.

(6) Thu 13/03/08 (Dan A.)       Dynamic randomized algorithms
Insertions and deletions, combination of conflict and influence graphs, example: trapezoidal map of line segments.

(7) Thu 20/03/08 (Gill B.)       Formulae and growth rates of polycubes

(8) Thu 27/03/08 (Itay B.-D.)       Davenport-Schinzel sequences (alternative link)
Complexity of Davenport-Schinzel sequences, applications: lower envelopes, nearest-neighbor among moving points, a cell in an arrangement of line segments, geometric graphs.