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

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

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

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