Discrete Algorithmic Geometry - 238739
Prof. Gill Barequet (barequet@cs.technion.ac.il)
Spring 2016

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

(23/Jun/16) 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!).

(20/Jun/16) Ben will give a short compensation lecture on Wednesday, June 22, 2016, in T-301 (not T-401!) at 9:30.

(07/Apr/16) The remaining meetings of the course will start at 11:30.

(18/Mar/16) Meetings of the course will be held on Mondays at 10:30 in T-401. Please contact me this week for lecture assignments.

(14/Mar/16) The first meeting of the course will be held on Tuesday 15/3 at 12:30 in T-301.


Bibliography

  1. Main text book:
    J.-D. Boissonnat and M. Yvinec, Algorithmic Geometry, Cambridge University Press, UK, 1998.
  2. A focus on D.S. sequences:
    M. Sharir and P.K. Agarwal, Davenport-Schinzel Sequences and Their Geometric Applications, Cambridge University Press, 1995.
  3. A few papers.

Library links

Grading Policy

Class performance: 70%.
Final quiz: 30% (date: July 12, 2016).

Course Summary

(1) Tuesday 15/Mar/16 (Gill B.)       Introduction
Overview of the course, polyominoes and polycubes
Papers on Heilbronn's problem:
G. Barequet, A lower bound for Heilbronn's triangle problem in d dimensions, SIAM J. on Discrete Mathematics, 14 (2), 230-236, 2001. paper
G. Barequet, The on-line Heilbronn's triangle problem, Discrete Mathematics, 283 (1-3), 7-14, June 2004. paper
G. Barequet and A. Shaikhet, The on-line Heilbronn's triangle problem in d dimensions, Discrete & Computational Geometry, 38 (1), 51-60, July 2007. paper

(2-4) 21/3+28/3+4/4+9/5 (Gill B.)       More on polyominoes and polycubes
Papers: 1, 2, 3, 4, 5, 6, 7, 8

(5) Monday 11/Apr/16 (Mira S.)       Proper polycubes

(6) 16/5 (Gill B.)       Davenport-Schinzel sequences

(7) 23/5 (guest)       The probabilistic method
Several applications of the probabilistic method to geometric problems.

(8) Monday 18/Apr/16 (Michael A.)       Random sampling
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. Presentations: 1, 2