Combinatorics of Arrangements - Recent Progress

Micha Sharir (TelAviv University,Israel)

Cutting Circles into Pseudo-segments and Improved Bounds for Incidences [.ps]

An Improved Bound for k-sets in Three Dimensions [.ps]

Arrangements of curves and surfaces have been a major topic of study in computational and combinatorial geometry for more than 15 years. The field has progressed from analysis of two-dimensional arrangements in the 80's and early 90's to analysis of arrangements in three and higher dimensions. The progress included sharp bounds on the complexity of lower envelopes, single cells, zones, vertical decompositions, as well as finding many applications of these bounds to diverse areas, such as motion planning and geometric optimization. In the past couple of years more progress has been made on various major problems in the combinatorics of arrangements, and the purpose of this talk is to survey some of this progress. The main topics that I will survey are:

  • The k-set problem: A lot of new results have been obtained, starting with Dey's improved bound for k-sets in the plane, and including an improved bound in 3 dimensions, an improved lower bound in the plane, connection between k-sets and deep results in the theory of polytopes, and improved bounds on levels in arrangements of curves.
  • Incidences between points and curves: I will survey recent progress on this problem, including improved bounds for incidences between points and circles and several related problems. I will also mention new results concerning bounds on the number of k-simplices spanned by a point set in d dimensions that are congruent to a fixed simplex.