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 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
(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 seminar-like.) 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 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: 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 off-line 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. 28-29)
G. Barequet,
A lower bound for Heilbronn's triangle problem in d dimensions,
SIAM J. on Discrete Mathematics,
14 (2001), 230-236.
(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), 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)
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)
-
(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, off-line and on-line 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 non-Euclidean
metrics
-
Power of points w.r.t. spheres, the paraboloid in one higher dimension and
the Voronoi diagram, Delaunay complexes, high-order 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.)
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.