Discrete Algorithmic Geometry - 236739
Prof. Gill Barequet
(barequet@cs.technion.ac.il)
Fall 2007-08
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, 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,
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.