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 DavenportSchinzel
sequences, Voronoi diagrams with Euclidean and nonEuclidean 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 T601 at 10:30 (note location and time!).
(20/Jun/16)
Ben will give a short compensation lecture on Wednesday, June 22, 2016,
in T301 (not T401!) 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 T401.
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 T301.
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: 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), 230236, 2001.
paper
G. Barequet,
The online Heilbronn's triangle problem,
Discrete Mathematics,
283 (13), 714, June 2004.
paper
G. Barequet and A. Shaikhet,
The online Heilbronn's triangle problem in d dimensions,
Discrete & Computational Geometry,
38 (1), 5160, July 2007.
paper

(24) 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.)
DavenportSchinzel 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.

(910) Monay 2/May/16 (Michael A.)
Randomized algorithms (same .ppt file as above)

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

(1113) 30/5+6/6+20/6+22/6 (Ben L.)
Incremental convex hulls

A deterministic algorithm, online and dynamic convex hulls.
Presentations:
1,
2