Separable partitions

For each fixed p and d, the maximum possible number rp,d(n) of separable partitions into p parts of n points in real d-space up to a constant factor is determined.

Abstract

An ordered partition of a set of n points in the d-dimensional Euclidean space is called a separable partition if the convex hulls of the parts are pairwise disjoint. For each fixed p and d we determine the maximum possible number rp.d(n) of separable partitions into p parts of n points in real d-space up to a constant factor. Of particular interest are the values rp, d(n) = ⊖(nd(p2)) for every fixed p and d ⩾ 3, and rp, 2(n) = ⊖(n6p −12) for every fixed p ⩾ 3. We establish similar results for spaces of finite Vapnik-Chervonenkis dimension and study the corresponding problem for points on the moment curve as well.