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
-
Main text book:
J.-D. Boissonnat and M. Yvinec,
Algorithmic Geometry,
Cambridge University Press, UK, 1998.
-
A focus on D.S. sequences:
M. Sharir and P.K. Agarwal,
Davenport-Schinzel Sequences and Their Geometric Applications,
Cambridge University Press, 1995.
-
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.