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


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

(29/JUN/11) Final grades will be transfered to the secretariat tomorrow, June 30.

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


  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)