Discrete Algorithmic Geometry - 238739
Prof. Gill Barequet (barequet@cs.technion.ac.il)
Spring 2011

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

(04/JUN/11) In both final quiz (20/6) and final exam (29/6) of the course you will not be allowed to use books or slide printouts, but will be allowed to bring ten (10) printed or hand-written A4 pages. (These pages should not include small photocopies of either book pages or slide printouts.)

(26/APR/11) Two make-up classes will be given in Wednesdays, April 27 and May 4, 2011. Both will be held in Taub 4 at 12:30, and the guest speaker in both will be Gadi Aleksandrowicz. He will talk about The Probabilsitic Method and its applications to geometric problems.

(27/MAR/11) Reminder: the meeting of tomorrow is canceled.

(10/MAR/11) Relevant links to papers are put after their citations.

(09/MAR/11) The planned-ahead schedule of the course can be found here.

(01/MAR/11) Please register to the mailing list, so that we can start with talk allocation.

(12/Dec/10) All students (including free listeners) are kindly asked to join the mailing list of the course. For this to happen, please e-mail me your full name, id #, faculty, and degree toward which you study. (This is in addition to the formal registration to the course! One can leave this mailing list at any time.)

Bibliography

1. Main text book:
   J.-D. Boissonnat and M. Yvinec, Algorithmic Geometry, Cambridge University Press, UK, 1998.
2. A focus on D.S. sequences:
   M. Sharir and P.K. Agarwal, Davenport-Schinzel Sequences and Their Geometric Applications, Cambridge University Press, 1995.
3. A few papers.

Library links

Grading Policy

Class performance (talk) and class attendance (3 absences allowed): 70%.
Final quiz and Final exam: 30% (June 20, 2011 [during class time], and June 29, 2011).

Course Summary

(1) Mon 28/FEB/11 (Gill B.)       Introduction; Heilbronn's triangle problem

A lower bound for the off-line Heilbronn's triangle problem in 2D.
N. Alon and J.H. Spencer, The Probabilistic Method, John Wiley & Sons, 1992. (sec. 3.3, p. 30)

(2) Mon 07/MAR/11 (Gill B.)       Polyominoes

Redelmeier's and Jensen's algorithms for counting polyominoes
D.H. Redelmeier, Counting polyominoes: Yet another attack, Discrete Mathematics, 36 (1981), 191-203. (paper)
G. Aleksandrowicz and G. Barequet, Counting polycubes without the dimensionality curse, Discrete Mathematics, 309 (2009), 4576-4583. (paper)
I. Jensen, Enumerations of lattice animals and trees, J. of Statistical Physics, 102 (2001), 865-881. (paper)
Counting polyominoes: A parallel implementation for cluster computing, Proc. Int. Conf. on Computational Science, III, Melbourne, Australia and St. Petersburg, Russia, Lecture Notes in Computer Science, 2659, Springer, 203-212, June 2003. (paper)

(3) Thu 14/Mar/11 (Yaniv S.)       Random Sampling

Basic concepts, the sampling theorem, the moment theorem.

(4) Mon 21/MAR/11 (Gill B.) Polyominoes and Polycubes

50 years of counting polyominoes and polycubes (several papers are available here)

(5) Mon 4/APR/11 (Rouven S.)       Randomized Algorithms

Conflict and influence graphs, off-line and on-line algorithms, example: trapezoidal map of line segments.

(6) Mon 11/APR/11 (Gill B.)       Heilbronn's triangle problem

Lower bounds for the on-line Heilbronn's triangle problem.
W.M. Schmidt, On a problem of Heilbronn, J. London Mathematical Society (2), 4 (1971), 545-550.
G. Barequet, The on-line Heilbronn's triangle problem, Discrete Mathematics, 283 (2004), 7-14. (paper)
G. Barequet and A. Shaikhet, The on-line Heilbronn's triangle problem in d dimensions, Discrete & Computational Geometry, 38 (2007), 51-60. (paper)

(7) Wed 27/APR/11 and Wed 4/MAY/11 (Gadi A.)       The probabilistic method

Several applications of the probabilistic method to geometric problems.

(8) Wed 11/May/11 and Mon 16/May/11 (Maor G.)       Convex hulls in 2 and 3 dimensions

Incremental convex hulls, divide-and-conquer convex hulls, convex hull of a polyline.

(9) Mon 16/May/11 and Mon 23/May/11 (Raeda N.)       Linear programming

Randomized linear programming, convex hulls using a shelling.

(10) Mon 30/May/11 (Gill B.)       Davenport-Schinzel sequences

Complexity of Davenport-Schinzel sequences, applications: lower envelopes, nearest-neighbor among moving points, a cell in an arrangement of line segments, geometric graphs.

(11) Mon 6/Jun/11 (Gill B.)       Heilbronn's triangle problem A lower bound for the off-line Heilbronn's triangle problem.
G. Barequet, A lower bound for Heilbronn's triangle problem in d dimensions, SIAM J. on Discrete Mathematics, 14 (2001), 230-236. (paper)