Entering and leaving j-facets

Let S be a set of n points in d-space, no i + 1 points on a common (i - 1)- flat for 1 less than or equal to i less than or equal to d. An oriented (d - 1)-simplex spanned by d points in S is called a j-facet of S if there are exactly j points from S on the positive side of its affine hull. We show: (*) For j less than or equal to n/2 - 2, the total number of (less than or equal to j)-facets (i.e. the number of i-facets with 0 less than or equal t o i less than or equal to j) in 3-space is maximized in convex position (wh ere these numbers are known). A large part of this presentation is a prepar atory review of some basic properties of the collection of j-facets-some wi th their proofs-and of relations to well-established concepts and results f rom the theory of convex polytopes (h-vector, Dehn-Sommerville relations, U pper Bound Theorem, Generalized Lower Bound Theorem). The relations are est ablished via a duality closely related to the Gale transform-similar to pre vious works by Lee, by Clarkson, and by Mulmuley. A central definition is as follows. Given a directed line l and a j-facet F of S, we say that l enters F if l intersects the relative interior of F in a single point, and if l is directed from the positive to the negative sid e of F. One of the results reviewed is a tight upper bound of ((j+d-1)(d-1) ) on the maximum number of j-facets entered by a directed line. Based on these considerations, we also introduce a vector for a point relat ive to a point set, which-intuitively speaking-expresses "how interior" the point is relative to the point set. This concept allows us to show that st atement (*) above is equivalent to the Generalized Lower Bound Theorem for d-polytopes with at most d + 4 vertices.