ICM 1998, Berlin, Aug. 18–27

Abstracts of Plenary and Invited Lectures

Section:

14. Mathematical Aspects of Computer Science

1991 MS Classification: 52C10, 52B05, 52B55, 68R05, 68Q25, 68U05 Welzl, Emo, ETH Zürich, Switzerland Halving Point Sets

The talk will discuss a problem that ermerged from combinatorial geometry around 1970, and which is popular and relevant in computational geometry. Consider first the following algorithmic problem. Given n points in ℝ^{d}, we want to find a hyperplane that minimizes the sum of Euclidean distances to these n points. A glimpse of reflection tells us that an optimal hyperplane cannot have a majority (⌊n/2⌋ + 1 or more) of the points on either side; otherwise a parallel motion towards this side will improve its quality. A hyperplane with at most ⌊n/2⌋ points on either side is called halving. How many partitions of a point set (into the points on one side, on the hyperplane, and on the other side) by halving hyperplanes can be realized by an n-point set in ℝ^{d}? The notions and results mentioned below are closely related to this question. Emphasis in the presentation is on techniques that may be useful elsewhere, and on interconnections to other topics in discrete geometry. Halving edges and a crossing lemma. Let P be a set of n points in the plane, n even, and no three points on a line. A halving edge is an undirected edge between two points, such that the connecting line has the same number of points on either side. Around 1970 L. Lovász, and in a more general setting with P. Erdős, A. Simmons, and E. G. Straus, were the first to investigate the geometric graph of halving edges of a point set, and proved that there cannot be more than O(n^{3/2}) such edges. Except for a small improvement to O(n^{3/2}/ log^{∗} n), there was no progress on the problem until T. Dey recently gave an upper bound of 2n^{4/3}. He shows that the graph of halving edges cannot have more than O(n^{2}) pairs of crossing edges. Then he employs a crossing lemma (due to M. Ajtai et al., 1982, and T. Leighton, 1983), which has a number of other applications: A geometric graph with n vertices and c pairs of crossing edges has at most O(max(n, \sqrt[3]{cn^{2}})) edges. We will present a short probabilistic proof of the crossing lemma, and a proof of the O(n^{2}) bound on the number of crossings via the following identity observed by B. Aronov and the author (inspired by Dey’s proof): 8c + ∑_{p∈P} (deg p)^{2} = n(n − 1), where deg p is the number of halving edges incident to point p, and c is the number of crossing pairs of halving edges. The corresponding problem of bounding the number of halving triangles of n points in ℝ^{3}, n odd, has also been investigated in a sequence of papers with a currently best bound of n^{8/3} due to T. Dey and H. Edelsbrunner, 1994. While this bound still allows for a simple proof, the situation gets more involved in dimensions 4 and higher, where the best results (see Agarwal et al., 1998) are based on a colored version of Tverberg’s Theorem by R. T. Živaljević and S. T. Vrećica, 1992. Lower bounds and oriented matroids. The upper bounds mentioned may be far from optimal. In the plane several constructions of n-point sets with Ω(n log n) halving edges are known. If we consider the corresponding problem for oriented matroids of rank 3 (or pseudoline arrangements in the dual), then there is an unpublished lower bound of n2^{Ω(\sqrt{log n})} due to M. Klawe, M. Paterson, and N. Pippenger, inspired by a connection to sorting networks. It is open whether this construction is realizable (stretchable) or not. j-Facets and the Upper Bound Theorem. The following notion generalizes halving edges and triangles. Let P be a set of n > d points in ℝ^{d} in general position, i. e., no d+1 points on a common hyperplane. A j-facet of P is an oriented (d − 1)-simplex spanned by d points in P that has exactly j points from P on the positive side of its affine hull. The 0-facets are the facets of the convex hull of P. Hence, the Upper Bound Theorem (P. McMullen, 1970) gives us a tight bound on the number of 0-facets, which is attained by the vertices of cyclic polytopes. Using their probabilistic technique, K. L. Clarkson and P. W. Shor, 1989, derive an asymptotically tight bound of O(n^{⌊d/2⌋}j^{⌈d/2⌉}) for the number of (≤ j)-facets (i. e., i-facets with 0 ≤ i ≤ j). However, except for dimensions 2 and 3, no exact bounds are known. In particular, it is not known whether the exact maximum is attained for sets in convex position or not. (It is still possible that the maximum is attained for points on the moment curve, where the number of (≤ j)-facets can be easily counted.) References. P. K. Agarwal, B. Aronov, T. M. Chan, and M. Sharir, On levels in arrangements of lines, segments, planes, and triangles, Discrete Comput. Geom. (1998), to appear. M. Ajtai, V. Chvátal, M. M. Newborn, and E. Szemerédi, Crossing-free subgraphs, Ann Discrete. Math. 12 (1982) 9–12. A. Andrzejak, B. Aronov, S. Har-Peled, R. Seidel, and E. Welzl, Results on k-sets and j-facets via continuous motion, in “Proc. 14th Ann. ACM Symp. on Comput. Geom. ” (1998), to appear. K. L. Clarkson and P. W. Shor, Applications of random sampling in computational geometry, II, Discrete Comput. Geom. 4 (1989) 387–421. T. K. Dey, Improved bounds for planar k-sets and related problems, in “Proc. 38th Ann. IEEE Symp. on Foundations of Comput. Sci. ” (1997) 156–161. T. K. Dey and H. Edelsbrunner, Counting triangle crossings and halving planes, Discrete Comput. Geom. 12 (1994) 281–289. P. Erdős, L. Lovász, A. Simmons, and E. G. Straus, Dissection graphs of planar point sets, in A Survey of Combinatorial Theory (Eds. J. N. Srivastava et al.), North Holland Publishing Company (1973) 139–149.

T. Leighton, Complexity Issues in VLSI, Foundation of Computing Series, MIT Press, Cambridge (1983). L. Lovász, On the number of halving lines, Ann. Universitatis Scientarium Budapest, Eötvös, Sectio Mathematica 14 (1971) 107–108. P. McMullen, The maximum number of faces of a convex polytope, Mathematika 18 (1970) 179–184. R. T. Živaljević and S. T. Vrećica, The colored Tverberg’s problem and complexes of injective functions, J. Combin. Theory Ser. A 61 (1992) 309–318.