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


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

(12/Jun/13) The final quiz will be held during the meeting of 18/06/2013.

(30/Apr/13) The lectures of 7/5, 21/5, 28/5, and 4/6 will last 3 hours instead of 2 hours, starting around 9:40.

(03/Mar/13) Students who intend to take the course are asked to meet me on Tuesday, March 5, 2013, or to correspond with me via email for assigning a topic for a lecture. (Each student will give a lecture; part of the course will be seminar-like.) Meeting me is preferred.

(04/Feb/13) I will miss the first two lectures of the semester due to a business trip. Arrangements for these lectures:
12/3/13: Lecture will be given by Dr. Gadi Aleksandrowicz.
19/3/13: Lecture is canceled. A compensation lecture will be given on Sunday, 24/3/13.

(16/Dec/12) All students (including free listeners) are kindly requested 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 exam: 30% (date: June 18, 2013).

Course Summary

(1) Tuesday 02/Apr/13 (Gill B.)       Introduction
Overview of the course

(2) Tuesday 09/Apr/13 (Gill B.)       Heilbronn's triangle problem
A lower bound for the off-line Heilbronn's triangle problem in two and higher dimensions.
N. Alon and J.H. Spencer, The Probabilistic Method, John Wiley & Sons, 1992. (sec. 3.3, pp. 28-29)
G. Barequet, A lower bound for Heilbronn's triangle problem in d dimensions, SIAM J. on Discrete Mathematics, 14 (2001), 230-236. (paper)

(3) Tuesday 23/Apr/13 (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)

(4) Tuesday 30/Apr/13 (Roi P.)       Random sampling
Basic concepts, the sampling theorem, the moment theorem.

(5a) Tuesday 07/May/13 (Roi P.)       Randomized algorithms
Conflict and influence graphs, off-line and on-line algorithms, example: trapezoidal map of line segments.

(5b) Tuesday 07/May/13 (Gill B.)       A lower bound on λ
Polyominoes on twisted cylinders.
G. Barequet, M. Moffie, A. Ribó, and G. Rote, Counting polyominoes on twisted cylinders, Integers: Electronic J. of Combinatorial Number Theory, 6, #A22, 37 pp., September 2006. (paper)

(6a) Tuesday 21/May/13 (Mira S.)       Dynamic randomized algorithms
Insertions and deletions, combination of conflict and influence graphs, example: trapezoidal map of line segments.

(6b) Tuesday 21/May/13 (Mira S.)       λ > 4
Running a program on a supercomputer in HPI, Potsdam.

(7) Tuesday 28/May/13 (Avi S.)       Voronoi diagrams - Euclidean and non-Euclidean metrics
Power of points w.r.t. spheres, the paraboloid in one higher dimension and the Voronoi diagram, Delaunay complexes, high-order Voronoi diagrams.
Power diagrams, affine diagrams, weighted diagrams, L_1 and L_infty.

(8) Tuesday 04/Jun/13 (Gadi A.)       The probabilistic method
Several applications of the probabilistic method to geometric problems.

(9) Tuesday 11/Jun/13 (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.