Separable partitions

Separable partitions

0.00 Avg rating0 Votes
Article ID: iaor20001791
Country: Netherlands
Volume: 91
Issue: 1/3
Start Page Number: 39
End Page Number: 51
Publication Date: Jan 1999
Journal: Discrete Applied Mathematics
Authors: ,
Keywords: programming: convex
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(p/2)) 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.

Reviews

Required fields are marked *. Your email address will not be published.