Results on -Sets and -Facets via Continuous Motion
Artur Andrzejak, Eth Zurich Zurich, Boris S. Aronov, Peter York, Sariel Har-Peled, Paul C. Canfield, Raimund Seidel, Emo Welzl · 1997
Let be a set of points in in general position, i.e., no points on a common -flat, . A -set of is a set of points in that can be separated from by a hyperplane. A -facet of is an oriented simplex spanned by points in which has exactly points from on the positive side of its affine hull. If is a planar point set and is even, a halving edge is an undirected edge between two points, such that the connecting line has the same number of points on either side. The number of -sets is twice the number of halving edges. Inspired by Dey’s recent proof of a new bound on the number of -sets we show that where is the number of halving edges incident to point and is the number of crossing pairs of halving edges. The identity allows us, among other things, to determine the maximum number of halving edges in a set of 12 points. An analogous identity holds for -facets. For in we show that for the number of ( )-facets (i.e., -facets with ) is maximized for sets in convex position, where this number is known to be For , is the tight upper bound for the number of -sets (i.e., -sets with ). Part of this work was performed while R.S. and E.W. were visiting the DIMACS center in November 1989, while R.S. visited FU Berlin in 1992, while E.W. visited Tel Aviv University in February 1994, while A.A. and E.W. were still at FU Berlin, and while B.A. was visiting ETH in April 1997. B.A. has been partially supported by a Sloan Research Fellowship. E.W. has been partially supported by a Max-Planck Research Prize. Finally we discuss the relation between the vector of numbers of -sets, and the vector of numbers of -facets, for a given point set. In the plane the number of -sets equals the number of facets. In the -set vector determines the -facet vector (and vice versa) by a linear relation. There is no such relation in for exceeding 3. These results can be obtained by arguments via continuous motion of one point set to another while observing certain quantities related to -sets and -facets. For the relation between -sets and -facets in , we give a more direct argument via so-called -set polytopes.