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


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

(03/May/15) Note the change in the dates of lectures 5 and 6: They moved from 13/5 and 20/5 to 6/5 and 13/5, respectively.

(21/Mar/15) Students who intend to take the course are asked to meet me on Sunday, March 22, 2015 for assigning a topic for a lecture. (Each student will give two lecture; part of the course will be in the form of a seminar.)

(10/Dec/14) 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: ??? ??, 201?).

Course Summary

(1) Wednesday 25/Mar/15 (Gill B.)       Introduction
Overview of the course, polyominoes and polycubes

(2) Wednesday 1/Apr/15 (Gill B.)       More on polyominoes and polycubes

(3) Wednesday 15/Apr/15 (Vsevolod R.)       Random sampling
Basic concepts, the sampling theorem, the moment theorem.

(4) Wednesday 29/Apr/15 (Vsevolod R.)       Randomized algorithms
Conflict and influence graphs, off-line and on-line algorithms, example: trapezoidal map of line segments.

(5) Wednesday 6/May/15 (Gill B.)       Heilbronn's triangle problem
An upper bound, a lower bound by example.
A lower bound in the off-line case.
N. Alon and J.H. Spencer, The Probabilistic Method, John Wiley & Sons, 1992. (sec. 3.3, pp. 28-29)
A lower bound in the on-line case.
W.M. Schmidt, On a problem of Heilbronn, J. London Mathematical Society (2}, 4 (1971), 545-550.

(6) Wednesday 13/May/15 (Nitzan T.)       Dynamic randomized algorithms
Insertions and deletions, combination of conflict and influence graphs, example: trapezoidal map of line segments.

(7) Wednesday 27/May/15 (Nitzan T.)       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.

(8) Sunday 31/May/15 (Gill)       Polycuebs
Formulae and growth rates of polycubes.

(9) Wednesday 3/Jun/15 (Gilad K.)       Voronoi diagrams - Euclidean metric
Power of points w.r.t. spheres, the paraboloid in one higher dimension and the Voronoi diagram, Delaunay complexes, high-order Voronoi diagrams.

(10) Wednesday 3/Jun/15 (back-to-back to #9) (Gill)       ???

(11) Wednesday 17/Jun/15 (Gilad K.)       Voronoi diagrams - Non-Euclidean metric
Power diagrams, affine diagrams, weighted diagrams, L_1 and L_infty.

(12) Wednesday ??/???/15 (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)
I. Jensen, 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)
G. Barequet and M. Moffie, On the complexity of Jensen's algorithm for counting fixed polyominoes, J. of Discrete Algorithms, 5 (2007), 348-355. (paper)

(13) Wednesday ??/???/15 (guest)       The probabilistic method
Several applications of the probabilistic method to geometric problems.