Incidences and Related Problems

Micha Sharir

Tel Aviv University

September 27,
refreshments at 3:45pm


We present several recent results, in which new bounds are derived for the number of incidences between points and curves in two and three dimensions, as well as several related results, where these new bounds are applied. We also review the recent history of the incidence problem and its relatives.

We first consider the problem of cutting circles and pseudocircles in the plane (closed Jordan curves, each pair of which intersect at most twice) into pseudo-segments, that is, arcs with the property that each pair of them intersect at most once. We derive new bounds for the number of cuts, which improve a general previous bound, due to Tamaki and Tokuyama.

Combining these results with Sz\'ekely's technique, which is based on crossing numbers of graphs, and with dual space partitioning techniques, we obtain improved bounds for incidences between points and circles, between points and parabolas, between points and pseudo-circles, and between points and graphs of polynomials of fixed maximum degree.

Similar bounds are also obtained for the complexity of many faces in arrangements of curves of these classes. Improved bounds are also derived for levels in such arrangements.

We also discuss algorithms for computing incidences and many faces in such arrangements. The algorithms make use of a new duality transform (related to an earlier one due to Goodman) between points and pseudolines. This transform has also several other applications.

We next consider the problem of incidences between points and curves in three dimensions. This area has not been studied before, and we obtain a variety of new bounds for incidences between points and lines, between points and `equally-inclined' lines, between points and circles, and between points and certain kind of helices.

Finally, there are several additional applications of the new bounds. We mention two of them: A new lower bound for the number of distinct distances in three dimensions, and improved upper bounds for the number of simplices spanned by a point set in three or four dimensions and congruent to a given simplex.

Obviously, all of this will not fit into a single talk. In fact, we will most likely not even reach the middle of this abstract. The purpose of the abstract is to provide extra information for interested people.

Speaker's Contact Info: sharir(at-sign)

Return to seminar home page

Combinatorics Seminar, Mathematics Department, MIT, sara(at-sign)

Page loaded on August 26, 2002 at 06:51 PM. Copyright © 1998-99, Sara C. Billey. All rights reserved.