Discrete Algorithmic Geometry  236739
Prof. Gill Barequet
(barequet@cs.technion.ac.il)
Fall 200708
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, polyomino counting, and variants of Heilbronn's
triangle problem.
News and Messages
(07/02/08)
Note that the meeting of Thursday, February 14, is canceled.
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% (TBA).
Course Summary

(1) Mon 21/01/08 (Gill B.)
Introduction; Heilbronn's triangle problem

A lower bound for the online Heilbronn's triangle problem in 2D.
Source: W.M. Schmidt, On a problem of Heilbronn, J. London Mathematical
Society (2), 4 (1971), 545550.

(2) Mon 21/01/08, Thu 07/02/08 (Gadi A.)
The probabilistic method

Basic examples, a lower bound for the offline 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, offline and online algorithms,
example: trapezoidal map of line segments.

(5) Thu 06/03/08 (Gill B.)
Transfermatrix
algorithms

Counting polyominoes in 2D.
Source: I. Jensen, Enumerations of lattice animals and trees, J. of
Statistical Physics, 102 (2001), 865881.

(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.)
DavenportSchinzel sequences
(alternative link)

Complexity of DavenportSchinzel sequences, applications: lower envelopes,
nearestneighbor among moving points, a cell in an arrangement of line
segments, geometric graphs.