ICM 1998, Berlin, Aug. 18–27

Abstracts of Plenary and Invited Lectures

Section:

13. Combinatorics

1991 MS Classification: 52C99, 52C10, 68U05, 68R99 Matoušek, Jiří, Charles University, Prague, Czech Republic Mathematical snapshots from the computational geometry landscape

The aim of the talk is to introduce several mathematically interesting notions, techniques, and results that emerged in the field of computational geometry in recent years. Computational geometry is a branch of theoretical computer science considering the design of efficient algorithms for computing with configurations of simple geometric objects in Euclidean spaces. The space dimension is usually considered a constant, and many problems are studied mainly in the plane or in the 3-dimensional space. Computational geometry constituted sometimes around the year 1980 and it has been developing very rapidly since then. Although the main emphasis in this field is on algorithms, there are purely mathematical aspects which deserve to be known to a wider mathematical public. Quite subjectively, the speaker has selected several such topics for the talk (necessarily omitting many other, maybe even nicer things). Since the results to be mentioned include the ideas of a large number of researchers (speaker’s own results being a tiny part only), it is not possible to give explicit credits to all of the contributors, and names will be mentioned only occasionally. The first topic planned for the talk is the complexity of arrangements of geometric objects. For example, suppose that we have n arbitrary segments in the plane, and we consider one connected component of the complement of their union (a 2-dimensional cell of the arrangement). What is the maximum possible number of vertices (segments’ endpoints and intersections) on its boundary? This brings us to the long-studied combinatorial problem of Davenport-Schinzel sequences and their generalizations. Recently, there has been a considerable progress concerning higher-dimensional analogues and other variants of the problem. The second topic starts with the following problem. Given n lines in the plane and an number r > 1, cover the plane with as few (possibly unbounded) triangles as possible, in such a way that the interior of each triangle is intersected by no more than \frac{n}{r} of the lines. It turns out that one can always use O(r^{2}) triangles, and such a collection of triangles (called a (1/r)-cutting for the given collection of lines) can serve for subdividing a geometric or algorithmic problem concerning the given lines into smaller subproblems. For example, a simple proof of a result of Szemerédi and Trotter concerning the maximum possible number of incidences of n lines and n points can be given using (1/r)-cuttings (recently, a still simpler proof has been found using a lemma on the number of crossings in a graph drawing, but the technique with cuttings seems more generally applicable). Time permitting, some more topics will be mentioned, such as the so-called range searching problem and its surprising relations to Heilbronn’s problem in combinatorial geometry, or the attempts in computational geometry at efficient algorithms for linear programming, their abstract view, and how this led to an elegant proof of a difficult Helly-type result in convexity, or how a combination of algebraic techniques with results on the number of incidences of points and curves provides a better understanding of geometric configurations, where the straightness of straight lines (finally) matters. In the accompanying paper, a few other areas will also be surveyed, and basic bibliography will be provided.