The Caratheodory number for the k-core (Q2640883): Difference between revisions

S denotes a finite point set in d-space each of whose points is counted with a finite multiplicity. Its k-core is the intersection of all the convex hulls of subsets A of S for which the cardinality of \(S\setminus A\) is no more than k. The Carathéodory number f(d,k) of the k-core of S is the least integer with the property that if x is in the k-core of S, then there is a subset T of S, whose k-core contains x, for which the cardinality of T is no more than f(d,k). This paper determines bounds and special values for f(d,k): \((k+1)(d+1)\leq f(d,k)\leq d^{k+1},\) excepting on the right hand (d,k) is neither (2,1) nor (2,2); \(f(2,k)=3(k+1);\) \(f(d,1)=\max \{2(d+1),1+d+[d^ 2/4]\}.\) Also the authors provide asymptotic results as \(d\to \infty\) for fixed k and, for d fixed and \(\geq 5\), as \(k\to \infty\).