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
Since Ben's compensation lecture in 22/6 did not take place,
he will give it on Tuesday, June 28, 2016,
in T-601 at 10:30 (note location and time!).
Ben will give a short compensation lecture on Wednesday, June 22, 2016,
in T-301 (not T-401!) at 9:30.
The remaining meetings of the course will start at 11:30.
Meetings of the course will be held on Mondays at 10:30 in T-401.
Please contact me this week for lecture assignments.
The first meeting of the course will be held on Tuesday 15/3 at
12:30 in T-301.
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: 70%.
Final quiz: 30% (date: July 12, 2016).
(1) Tuesday 15/Mar/16 (Gill B.)
Overview of the course, polyominoes and polycubes
Papers on Heilbronn's problem:
A lower bound for Heilbronn's triangle problem in d dimensions,
SIAM J. on Discrete Mathematics,
14 (2), 230-236, 2001.
The on-line Heilbronn's triangle problem,
283 (1-3), 7-14, June 2004.
G. Barequet and A. Shaikhet,
The on-line Heilbronn's triangle problem in d dimensions,
Discrete & Computational Geometry,
38 (1), 51-60, July 2007.
(2-4) 21/3+28/3+4/4+9/5 (Gill B.)
More on polyominoes and polycubes
(5) Monday 11/Apr/16 (Mira S.)
(6) 16/5 (Gill B.)
(7) 23/5 (guest)
The probabilistic method
Several applications of the probabilistic method to geometric problems.
(8) Monday 18/Apr/16 (Michael A.)
Basic concepts, the sampling theorem, the moment theorem.
(9-10) Monay 2/May/16 (Michael A.)
Randomized algorithms (same .ppt file as above)
Conflict and influence graphs, off-line and on-line algorithms,
example: trapezoidal map of line segments.
(11-13) 30/5+6/6+20/6+22/6 (Ben L.)
Incremental convex hulls
A deterministic algorithm, on-line and dynamic convex hulls.