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 DavenportSchinzel
sequences, Voronoi diagrams with Euclidean and nonEuclidean 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 seminarlike.) 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 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: 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 offline 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. 2829)
G. Barequet,
A lower bound for Heilbronn's triangle problem in d dimensions,
SIAM J. on Discrete Mathematics,
14 (2001), 230236.
(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), 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)
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)

(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, offline and online 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 nonEuclidean
metrics

Power of points w.r.t. spheres, the paraboloid in one higher dimension and
the Voronoi diagram, Delaunay complexes, highorder 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.)
DavenportSchinzel
sequences

Complexity of DavenportSchinzel sequences, applications: lower envelopes,
nearestneighbor among moving points, a cell in an arrangement of line
segments, geometric graphs.