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 DavenportSchinzel
sequences, Voronoi diagrams with Euclidean and nonEuclidean 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 email 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,
DavenportSchinzel 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, offline and online 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 offline case.
N. Alon and J.H. Spencer, The Probabilistic Method,
John Wiley & Sons, 1992.
(sec. 3.3, pp. 2829)
A lower bound in the online case.
W.M. Schmidt, On a problem of Heilbronn,
J. London Mathematical Society (2},
4 (1971), 545550.

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

Complexity of DavenportSchinzel sequences, applications: lower envelopes,
nearestneighbor 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, highorder Voronoi diagrams.

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

???

(11) Wednesday 17/Jun/15 (Gilad K.)
Voronoi diagrams  NonEuclidean 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), 191203.
(paper)
G. Aleksandrowicz and G. Barequet,
Counting polycubes without the dimensionality curse,
Discrete Mathematics,
309 (2009), 45764583.
(paper)
I. Jensen,
Enumerations of lattice animals and trees,
J. of Statistical Physics,
102 (2001), 865881.
(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,
203212, 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), 348355.
(paper)

(13) Wednesday ??/???/15 (guest)
The probabilistic method

Several applications of the probabilistic method to geometric problems.