Prof. Micha Sharir (firstname.lastname@example.org)
Spring 2015, Monday 15:00-18:00, Orenstein 102
*** By popular demand, here are links to two past in-class exams:
Shi'ur khazara: Sunday, 21.6, 15--, Schreiber 309
Assignment 3 can be picked up from a shelf near the "open space" in the basement
The class in 18.5 is cancelled.
Make-up class will be given on Friday, 29.5, 10--13, in Schreiber 008
Assignment grader: Omer Gold
Please address all special requests to Omer, cc'ed to me.
Solution sketches (so far for assignments 1 and 2)
brief solutions of assignment 1
brief solutions of assignment 2
brief solutions of assignment 3
brief solutions of assignment 4
brief solutions of assignment 5
*** Here are lecture notes, taken by one of the
students six years ago.
*** The notes are offered as a public service; they are not edited
*** and the "management" is not responsible for their contents...
*** The course this year may slightly deviate from the material presented in these notes!
Lecture 1 (3.11.08)
Lecture 2 (10.11.08)
Lecture 3 (17.11.08)
Lecture 4 (24.11.08)
Lecture 5 (1.12.08)
Lecture 5--different version (1.12.08)
Lecture 6 (8.12.08)
Lecture 7 (15.12.08)
Lecture 8 (22.12.08)
Lecture 9 (29.12.08)
Lecture 10 (5.1.09)
Lecture 10 (partial) (5.1.09)
Lecture 11 (12.1.09)
Lecture 12 (19.1.09)
Lecture 13 (26.1.09)
*** By popular demand, here are links to two past (take-home) exams:
5 assignments will be given. They comprise about 20% of the final
Assignment 1, due April 13, 2015
Assignment 2, due May 4, 2015
Assignment 3, due May 29, 2015
Assignment 4, due June 15, 2015
Assignment 5, due June 29, 2015 (in Omer's mailbox or by email to him)
Expected size of the convex hull of random points
Sarnak-Tarjan paper on persistent search trees
Final Exam: Moed Alef: June 23, 2015
An in-class exam
You may bring to the exam any written material
The exam comprises 80% of the final grade.
Moed Bet: July 24, 2015
The course is a basic course in computational geometry.
It assumes basic knowledge in algorithms, data structures, complexity,
Basic knowledge of probability is also needed.
It also assumes familiarity with basic geometric concepts and facts (in the plane and in higher dimensions).
There is no textbook that covers all the material given in the course, but a large portion of it is covered in the book:
De Berg, van Kreveld, Overmars and Schwarzkopf,
Computational Geometry, Algorithms and Applications (1997);
second edition (2000)
third edition (2008)
Additional material will be distributed or given a reference to, as
One may also consult the books
Final in-class exam and five assignments during the semester (see above).
Assignments will be graded and will comprise part (about 20 percent) of the final grade.
The syllabus of the course
(2) Convex Hull Algorithms:
(3) The Sweeping Paradigm:
(4) Point Location:
(5) Intersection Problems and Linear Programming:
(6) Voronoi Diagrams:
(7) Range Queries and Multidimensional Data Structures: