Advanced Topics in Computational and Combinatorial Geometry

                                           Prof. Micha Sharir  (
                                            Spring 2016, Monday 16:00-19:00, Shenkar / Physics 222



An earlier Exam

Brief solutions and hints are being posted below (July 7)

Shi'ur khazara: July 11 (Monday), 16-19, schreiber 309

The graded assignments 4 are now available in Orit Raz's mailbox, Schreiber, 1st floor, near the elevator (July 3)

The graded assignments 3 are now available in Orit Raz's mailbox, Schreiber, 1st floor, near the elevator (June 5)

Assignment 5 is now available (May 31)

Assignment 4 is now available (May 10)

A make-up class will be held on Friday, May 20, 9:30--12, Schreiber 008.
This replaces the class on June 6, which will be cancelled because of some noisy event on campus.

Assignment 3 is now available (April 14)

*** Change of hours: *** See above for the new hours 16-19, effective from March 28!
(Not to be confused with the shift to daylight saving time!)

FINAL EXAM: In-class exam, Moed A: July 17, 2016.

FINAL EXAM: Moed B: September 18, 2016.

*** NOTE: **** Short solutions and hints to the exercises will be provided later.

Homework 1:

Homework 2:

Homework 3:

Homework 4:

PREVIOUS FINAL EXAMS: These are take-home exams, and are therefore probably harder (in principle) than the expected level of the exam.

Old Exam 1:

Old Exam 2:


The following are notes of the lectures given in this course in 2012.
No responsibility for the contents and/or for how much they match the present lectures.
But hopefully they might be of some help.


Lecture 1, scanned notes (courtesy of Igor Tubis)

Lecture 2, scanned notes

Lecture 3, scanned notes

Lecture 4, scanned notes

Lecture 5, scanned notes

Lecture 6, scanned notes

Lecture 7, scanned notes

Lecture 8, scanned notes

Lecture 9, scanned notes

Lecture 10, scanned notes

Lecture 11, scanned notes

Lecture 12, scanned notes

Lecture 13, scanned notes

Lecture 14, scanned notes

Lecture 15, scanned notes

Seth Pettie's best bounds for DS sequences

The lower bound construction from the book


Assignment 1: Due March 28, 2016

Assignment 2: Due April 11, 2016

Assignment 3: Due May 9, 2016

Assignment 4: Due May 30, 2016

Assignment 5: Due June 30, 2016 (in my mailbox or in Orit's mailbox)


The course is a continuation of the course  Computational Geometry, which is the only pre-requisite for the course.

There is no textbook that covers all the material given in the course, but a large portion of it is covered in the book:

M. Sharir and P.K. Agarwal,
Davenport-Schinzel Sequences and their Geometric Applications,
Cambridge University Press, New York, 1995.

Additional material can be found in the books

J. Pach and P.K. Agarwal,
Combinatorial Geometry,
Wiley Interscience, New York, 1995

J. Matousek,
Lectures on Discrete Geometry,
Springer, Berlin 2002

Additional material will be distributed or given a reference to, as needed.
One may also consult the books

The grade will be based on a final exam and on exercises (assignments) given during the semester.

The syllabus of the course

(1) Arrangements:


(2) Davenport-Schinzel Sequences and Envelopes:


(3) Two-Dimensional Arrangements:


(4) The Clarkson-Shor Theorem and its Applications:


(5) Higher-Dimensional Arrangements:


(6) The Zone Theorem and its Extensions:


(7) Miscellaneous Results in Higher-Dimensional Arrangements:


(8) Randomized Techniques in Geometry:


(9) Incidences, Levels, and Complexity of Many Cells in Arrangements:


(10) Partitioning Arrangements, Range Searching, and Related Problems:


(11) Applications: