Discrete Algorithmic Geometry - 238739
Prof. Gill Barequet
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
News and Messages
Final grades will be transfered to the secretariat tomorrow, June 30.
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 hand-written A4 pages. (These pages should
not include small photocopies of either book pages or slide printouts.)
Two make-up 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.
Reminder: the meeting of tomorrow is canceled.
Relevant links to papers are put after their citations.
The planned-ahead schedule of the course can be found
Please register to the mailing list, so that we can start with talk
All students (including free listeners) are kindly asked 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.)
Main text book:
J.-D. Boissonnat and M. Yvinec,
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.
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).
(1) Mon 28/FEB/11 (Gill B.)
Introduction; Heilbronn's triangle problem
A lower bound for the off-line Heilbronn's triangle problem
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.)
Redelmeier's and Jensen's algorithms for counting polyominoes
Counting polyominoes: Yet another attack,
36 (1981), 191-203.
G. Aleksandrowicz and G. Barequet,
Counting polycubes without the dimensionality curse,
309 (2009), 4576-4583.
Enumerations of lattice animals and trees,
J. of Statistical Physics,
102 (2001), 865-881.
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.
(3) Thu 14/Mar/11 (Yaniv S.)
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
(5) Mon 4/APR/11 (Rouven S.)
Conflict and influence graphs, off-line and on-line algorithms,
example: trapezoidal map of line segments.
(6) Mon 11/APR/11 (Gill B.)
Heilbronn's triangle problem
Lower bounds for the on-line Heilbronn's triangle problem.
On a problem of Heilbronn,
J. London Mathematical Society (2),
4 (1971), 545-550.
The on-line Heilbronn's triangle problem,
283 (2004), 7-14.
G. Barequet and A. Shaikhet,
The on-line Heilbronn's triangle problem in d dimensions,
Discrete & Computational Geometry,
38 (2007), 51-60.
(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
Incremental convex hulls, divide-and-conquer convex hulls,
convex hull of a polyline.
(9) Mon 16/May/11 and Mon 23/May/11 (Raeda N.)
Randomized linear programming, convex hulls using a shelling.
(10) Mon 30/May/11 (Gill B.)
Complexity of Davenport-Schinzel sequences, applications: lower envelopes,
nearest-neighbor 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 off-line Heilbronn's triangle problem.
A lower bound for Heilbronn's triangle problem in d dimensions,
SIAM J. on Discrete Mathematics,
14 (2001), 230-236.