Results on k-sets and j-facets via continuous motion
Artur Andrzejak, Boris S. Aronov, Sariel Har-Peled, Raimund Seidel, Emo Welzl · 1998
Let P be a set of n. points in IRd in general position, i.e., no i + 1 points on a common (i -1)-flat, 1 < i 5 d.A k-set @'P is a set S of E points in P that can be separated from P \ S by a hyperplane.A j-facet of P is an oriented (d -l)simplex spanned by d points in P which has exactly j points from P on the positive side of its affine hull.If P is a planar point set and n 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 (n/2)-sets is twice the number of halving edges.Inspired by Dey's recent proof of a new bound on the number of k-sets we show that where degp is the number of halving edges incident to point p and C is the number of crossing pairs of halving edges.The identity allows us, among other things, to determine the masimum number of halving edges in a set of 12 points.An anaIogous identity holds for j-facets.For P in IR3 we show that for j 5 n/4 -2 the number of cs j)-facets (i.e., i-facets with 0 5 i 5 j) is maximized for sets in convex position, where this number is known to be (j + l)(j + 2)n -2(j + l)(j + 2)(j + 3)/3.For 1; 5 n/4 -1, k2n -k(k -1)(2A + 5)/3 is the tight upper bound for the number of (5 A)-sets (i.e., i-sets with 1 ': i 5 k).'h't of this work %S Performed while R.S. and E.W. were visiting the DlhfAa center in November 1989.while R.S. visited FU Berlin in 1992, while E.W. visited