Discrete Algorithmic Geometry  238739
Prof. Gill Barequet
(barequet@cs.technion.ac.il)
Spring 2011
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
(29/JUN/11)
Final grades will be transfered to the secretariat tomorrow, June 30.
(04/JUN/11)
In both final quiz (20/6) and final exam (29/6) of the course you will
not be allowed to use books or slide printouts, but will be allowed
to bring ten (10) printed or handwritten A4 pages. (These pages should
not include small photocopies of either book pages or slide printouts.)
(26/APR/11)
Two makeup classes will be given in Wednesdays, April 27 and
May 4, 2011. Both will be held in Taub 4 at 12:30, and the guest speaker
in both will be Gadi Aleksandrowicz. He will talk about The Probabilsitic
Method and its applications to geometric problems.
(27/MAR/11)
Reminder: the meeting of tomorrow is canceled.
(10/MAR/11)
Relevant links to papers are put after their citations.
(09/MAR/11)
The plannedahead schedule of the course can be found
here.
(01/MAR/11)
Please register to the mailing list, so that we can start with talk
allocation.
(12/Dec/10)
All students (including free listeners) are kindly asked 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 quiz and Final exam: 30% (June 20, 2011 [during class time], and
June 29, 2011).
Course Summary

(1) Mon 28/FEB/11 (Gill B.)
Introduction; Heilbronn's triangle problem

A lower bound for the offline Heilbronn's triangle problem
in 2D.
N. Alon and J.H. Spencer, The Probabilistic Method,
John Wiley & Sons, 1992.
(sec. 3.3, p. 30)


(2) Mon 07/MAR/11 (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)


(3) Thu 14/Mar/11 (Yaniv S.)
Random Sampling

Basic concepts, the sampling theorem, the moment theorem.

(4) Mon 21/MAR/11 (Gill B.)
Polyominoes and Polycubes

50 years of counting polyominoes and polycubes (several papers are available
here)

(5) Mon 4/APR/11 (Rouven S.)
Randomized Algorithms

Conflict and influence graphs, offline and online algorithms,
example: trapezoidal map of line segments.

(6) Mon 11/APR/11 (Gill B.)
Heilbronn's triangle problem

Lower bounds for the online Heilbronn's triangle problem.
W.M. Schmidt,
On a problem of Heilbronn,
J. London Mathematical Society (2),
4 (1971), 545550.
G. Barequet,
The online Heilbronn's triangle problem,
Discrete Mathematics,
283 (2004), 714.
(paper)
G. Barequet and A. Shaikhet,
The online Heilbronn's triangle problem in d dimensions,
Discrete & Computational Geometry,
38 (2007), 5160.
(paper)

(7) Wed 27/APR/11 and Wed 4/MAY/11 (Gadi A.)
The probabilistic method

Several applications of the probabilistic method to geometric problems.

(8) Wed 11/May/11 and Mon 16/May/11 (Maor G.)
Convex hulls in 2 and 3
dimensions

Incremental convex hulls, divideandconquer convex hulls,
convex hull of a polyline.

(9) Mon 16/May/11 and Mon 23/May/11 (Raeda N.)
Linear programming

Randomized linear programming, convex hulls using a shelling.

(10) Mon 30/May/11 (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.

(11) Mon 6/Jun/11 (Gill B.)
Heilbronn's triangle problem
A lower bound for the offline Heilbronn's triangle problem.
G. Barequet,
A lower bound for Heilbronn's triangle problem in d dimensions,
SIAM J. on Discrete Mathematics,
14 (2001), 230236.
(paper)