Prof. Micha Sharir (firstname.lastname@example.org)
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.
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,
Wiley Interscience, New York, 1995
Lectures on Discrete Geometry,
Springer, Berlin 2002
Additional material will be distributed or given a reference to, as
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
(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: