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

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.

See also the site of graduate school.

News and Messages

(05/Jun/23) The strike is over; see updated schedule below.

(15/May/23) Note a few schedule changes in June:
Adi will give a lecture on Sunday, June 11, 2023, instead of on Thursday, June 29, 2023.
There will not be a lecture on Thursday, June 15, 2023.
Ohad will give a lecture on Thursday, June 22, 2023.
The lecture of Thursday, June 29, 2023 will be given either by me or by guest lecturer(s).

(23/Mar/23) A compensation lecture will be given via zoom (same zoom meeting number) on Sunday, March 26, 2023, at 8:30am.

(22/Mar/23) Due to the national paralysis day planned for tomorrow, our meeting of tomorrow morning will be held via Zoom. The zoom meeting number was distributed by E-mail.

(22/Mar/23) The day+time set for our meetings are Thursday 8:30-10:30am. The meeting place will be Taub 401.

(8/Mar/23) Students who wish to join this graduate course are asked to contact me by March 21, 2023, even if they have not read this message, otherwise they risk not being admitted to the course.

(1/Mar/23) This is a graduate course (the only active 238 course in the CS department). It will be given as a semi-seminar, meaning talks will be split between the students and myself. A student's talk might occupy 2-4 hours, depending on the number of registered students. Please contact me as early as possible in order to fix the material of your talk(s). Please also register to the mailing list of the course. (This has nothing to do with the formal registration to the course!) For this purpose, please send me your full name, id number, which degree you pursue, and your mobile phone number.

(1/Mar/23)
Topics covered in the course will include:
1. Random sampling [BY98, ch.4]
2. Randomized algorithms [BY98, ch.5]
3. Dynamic randomized algorithms [BY98, ch.6]
4. Arrangements of segments and Davenport-Schinzel sequences [BY98, ch.15] + survey (+ [SA95] as a background)
5. The probabilistic method [AS00, a few sections]
Optional topics:
6. Incremental convex hulls [BY98, ch.8]
7. Voronoi diagrams - Euclidean metric [BY98, ch.17]
8. Voronoi diagrams - Non-Euclidean metrics [BY98, ch.18]
Topics covered by me:
9. Lattice animals
10. Heilbronn's triangle problem

See the tentative schedule here.

Bibliography

  1. Main text book [BY98]:
    J.-D. Boissonnat and M. Yvinec, Algorithmic Geometry, Cambridge University Press, UK, 1998.
  2. A focus on D.S. sequences [SA95]:
    M. Sharir and P.K. Agarwal, Davenport-Schinzel Sequences and Their Geometric Applications, Cambridge University Press, 1995.
  3. The Probabilistic Method [AS00]:
    N. Alon, J.H. Spencer, and P. Erdös, The Probabilistic Method (2nd ed.), John Wiley & Sons, 2000.
  4. A few papers.

Classes

The allocated time is Monday 10:30-12:30, at hall Taub 401.

Grading Policy

Class performance: 70%.
Final quiz: 30% (tentative date: TBA).

Course Summary

(1) Thursday 23/Mar/2023
      Gill B.: Introduction; Polyominoes and polycubes
(2) Sunday 26/Mar/2023 (note unusual day)
      Gill B.: Polyominoes and polycubes (cont.)
(3) Thursday 13/Apr/2023
      Gill B.: Heilbronn's triangle problem
(4) Thursday 20/Apr/2023
      Hadar Kaminski: Random sampling
      Gill: A lower bound on the growth constant of polyiamonds
(5) Thursday 27/Apr/2023
      Hadar Kaminski: Randomized algorithms
(6) Thursday 4/May/2023
      Noga Keren: Dynamic randomized algorithms
(7) Thursday 11/May/2023
      Adi Rivkin: Voronoi diagrams - Euclidean metric
(-) Thursday 1/Jun/2023
      (canceled due to the strike of the senior academic staff)
(8) Thursday 8/Jun/2023
      Noga Keren: The probabilistic method
(9) Sunday 11/Jun/2023 (note unusual day)
      Adi Rivkin: Voronoi diagrams - Non-Euclidean metrics
(10) Thursday 22/Jun/2023
      Ohad Sharon: Incremental convex hulls
(11) Thursday 29/Jun/2023
      Ohad Sharon: Arrangements of segments and Davenport-Schinzel sequences
(12) Thursday 6/Jul/2023
      Final quiz