Advanced Topics in Computational and Combinatorial Geometry
Prof. Micha Sharir (email@example.com)
Spring 2012, Tuesday 15:00-18:00, Shenkar / Physics 104
FINAL EXAM: In-class exam, Monday, July 30, 9:00.
*** NOTE: **** It is still possible (and encouraged) to submit exercise 5!
Please put it in my mailbox or email me as convenient.
*** NOTE: **** Please find below short solutions and hints to exercises 1--4.
Thanks to Tal for producing them!
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:
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
Assignment 1: Due March 27, 2012
Assignment 2: Due April 17, 2012
Assignment 3: Due May 15, 2012
Assignment 4: Due May 29, 2012
Assignment 5: Due June 19, 2012
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
- Edelsbrunner, Algorithms in Combinatorial Geometry,
- Preparata and Shamos, Computational Geometry, An Introduction
- De Berg, van Kreveld, Overmars and Schwarzkopf, Computational Geometry,
Algorithms and Applications.
(This book is nowadays the standard (introductory) textbook
in Computational Geometry.)
The grade will be based on a final exam and on
exercises (assignments) given during the semester.
The syllabus of the course
- Basic terminology involving arrangements of lines and of other curves
in the plane,
of hyperplanes and of surfaces in higher dimensions.
- Some examples of problems reduced to problems in arrangements:
Voronoi diagrams, motion planning, transversals, median line.
- Basic substructures in arrangements: Envelopes, zones, cells,
and other structures in arrangements.
- Overview of problems involving complexity in arrangements.
(2) Davenport-Schinzel Sequences and Envelopes:
- Definition. Connection with lower envelopes. Some easy bounds.
- The case s=3: derivation of both upper and lower bounds.
- Bounds for higher order sequences.
- Realization by line segments.
- Efficient construction of envelopes. Applications.
(3) Two-Dimensional Arrangements:
- Complexity of a single cell.
- Complexity of a zone (in line arrangements and in general).
- Incremental construction of arrangements.
- Computing a single cell in an arrangement.
- Combination lemma. Applications.
- The union of pseudo-disks.
(4) The Clarkson-Shor Theorem and its Applications:
- The theorem for levels in arrangements of lines
and in general settings.
- Applications to levels and other geometric situations.
- An alternative derivation of near-linear bounds for
complexity of envelopes.
(5) Higher-Dimensional Arrangements:
- Arrangements of algebraic or semi-algebraic surfaces.
- Complexity of envelopes of simplices.
- Complexity of envelopes of general surfaces.
(6) The Zone Theorem and its Extensions:
- Proof of the Zone Theorem for arrangements of hyperplanes in arbitrary
- Applications and extensions:
Sum of squares of cell complexities.
The zone of a surface in an arrangement of hyperplanes.
(7) Miscellaneous Results in Higher-Dimensional Arrangements:
- Single cells and arbitrary zones.
- Overlay of minimization diagrams.
- Generalized Voronoi diagrams.
- Union of geometric objects.
(This will be mostly review of results, with little or no proof.)
(8) Randomized Techniques in Geometry:
- Random samples and epsilon-nets. VC dimension.
- Applications of random sampling
(Haussler and Welzl; Clarkson; Clarkson and Shor).
- Randomized incremental constructions
(Clarkson-Shor, Seidel, Guibas-Knuth-Sharir).
(9) Incidences, Levels, and Complexity of Many Cells in Arrangements:
- The Crossing Lemma and Sz\'ekely's method.
- Incidences between points and lines.
- Complexity of many faces in arrangements of lines.
- Generalization to other curves and to higher dimensions.
- The unit distance problem in 2 and 3 dimensions.
- Complexity of levels in line arrangements---the $k$-set problem.
(10) Partitioning Arrangements, Range Searching, and Related Problems:
- Cuttings arrangements of lines and curves.
- Simplicial partitions of point sets.
- Efficient data structures for simplex range searching.
- Multilevel structures and their applications.
- Spanning trees with small crossing number and their applications.
- Partitioning arrangements of hyperplanes or surfaces in higher
- Repeated distances in three dimensions.
- Dynamic geometry.
- Visibility and ray shooting problems.
- And so on as time permits.