Prof. Micha Sharir  (michas@post.tau.ac.il)
                                            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!

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:

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,
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

• 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

(1) Arrangements:

• 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, levels
  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 dimensions.
• 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 dimensions.
  Vertical decompositions.

(11) Applications:

• Transversals.
• Repeated distances in three dimensions.
• Dynamic geometry.
• Visibility and ray shooting problems.
• And so on as time permits.