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

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

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

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