Prof. Micha Sharir (michas@post.tau.ac.il)

**Spring 2016, Monday 16:00-19:00, Shenkar / Physics 222**

__ANNOUNCEMENTS__

** 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.
**

** 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)
**

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

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