j-Facets of Finite Point Sets and the Upper Bound Theorem for Polytopes

by Emo Welzl (ETH Zurich)


Let P be a set of n>d points in R^d, no d+1 of them on a common hyperplane. A {j-facet of P} is an oriented simplex spanned by d points in P that has exactly j points from P on the positive side of its affine hull. The (maximum) numbers of j-facets in finite point configurations are relevant for the analysis of several algorithms in geometry. A first paper on the problem was published by L\'aszl\'o Lov\'asz in 1971, one year after Peter McMullen's proof of the Upper Bound Theorem appeared. In the above terminology, this theorem gives the maximum number of 0-facets of n points in d-space. In this talk we address the fact that the relation between the two problems is much closer -- via the so-called h-vector and the Bruggesser-Mani shellings used in the proof of the Upper Bound Theorem. A proof of the Upper Bound Theorem will be presented.

!!! Dieses Dokument stammt aus dem ETH Web-Archiv und wird nicht mehr gepflegt !!!
!!! This document is stored in the ETH Web archive and is no longer maintained !!!