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.