TY - JOUR

T1 - Inclusion–Exclusion Principles for Convex Hulls and the Euler Relation

AU - Kabluchko, Zakhar

AU - Last, Günter

AU - Zaporozhets, Dmitry

PY - 2017/9/1

Y1 - 2017/9/1

N2 - Consider n points X1, … , Xn in Rd and denote their convex hull by Π. We prove a number of inclusion–exclusion identities for the system of convex hulls Π I: = conv (Xi: i∈ I) , where I ranges over all subsets of { 1 , … , n}. For instance, denoting by ck(X) the number of k-element subcollections of (X1, … , Xn) whose convex hull contains a point X∈ Rd, we prove that (Formula Presented.) for allX in the relative interior of Π. This confirms a conjecture of Cowan (Adv Appl Probab 39(3):630–644, 2007) who proved the above formula for almost allX. We establish similar results for the number of polytopes Π J containing a given polytope Π I as an r-dimensional face, thus proving another conjecture of Cowan (Discrete Comput Geom 43(2):209–220, 2010). As a consequence, we derive inclusion–exclusion identities for the intrinsic volumes and the face numbers of the polytopes Π I. The main tool in our proofs is a formula for the alternating sum of the face numbers of a convex polytope intersected by an affine subspace. This formula generalizes the classical Euler–Schläfli–Poincaré relation and is of independent interest.

AB - Consider n points X1, … , Xn in Rd and denote their convex hull by Π. We prove a number of inclusion–exclusion identities for the system of convex hulls Π I: = conv (Xi: i∈ I) , where I ranges over all subsets of { 1 , … , n}. For instance, denoting by ck(X) the number of k-element subcollections of (X1, … , Xn) whose convex hull contains a point X∈ Rd, we prove that (Formula Presented.) for allX in the relative interior of Π. This confirms a conjecture of Cowan (Adv Appl Probab 39(3):630–644, 2007) who proved the above formula for almost allX. We establish similar results for the number of polytopes Π J containing a given polytope Π I as an r-dimensional face, thus proving another conjecture of Cowan (Discrete Comput Geom 43(2):209–220, 2010). As a consequence, we derive inclusion–exclusion identities for the intrinsic volumes and the face numbers of the polytopes Π I. The main tool in our proofs is a formula for the alternating sum of the face numbers of a convex polytope intersected by an affine subspace. This formula generalizes the classical Euler–Schläfli–Poincaré relation and is of independent interest.

KW - Convex hulls

KW - Cowan’s formula

KW - Euler characteristic

KW - Euler relation

KW - Faces

KW - Inclusion–exclusion principle

KW - Intrinsic volumes

KW - Polytopes

UR - http://www.scopus.com/inward/record.url?scp=85014575459&partnerID=8YFLogxK

U2 - 10.1007/s00454-017-9880-0

DO - 10.1007/s00454-017-9880-0

M3 - Article

AN - SCOPUS:85014575459

VL - 58

SP - 417

EP - 434

JO - Discrete and Computational Geometry

JF - Discrete and Computational Geometry

SN - 0179-5376

IS - 2

ER -