TY - JOUR

T1 - Separable partitions

AU - Alon, Noga

AU - Onn, Shmuel

N1 - Funding Information:
* Corresponding author. E-mail: [email protected].~l. ’ Research supported in part by a USA Israeli BSF grant, by a grant from the Israel Science Foundation and by the Hermann Minkowski Minerva Center for Geometry at Tel Awv University. z Research supported in part by the Mathematical Sciences Research Institute at Berkeley California through NSF Grant DMS-9022140, by the Fund for the Promotion of Research at the Technion and by a VPR Grant at the Technion.

PY - 1999

Y1 - 1999

N2 - 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(2p)) 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.

AB - 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(2p)) 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.

KW - Convex polytope

KW - Convexity space

KW - Davenport Schinzel sequence

KW - Moment curve

KW - Partition

KW - Vapnik-Chervonenkis dimension

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

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

U2 - 10.1016/S0166-218X(98)00142-5

DO - 10.1016/S0166-218X(98)00142-5

M3 - Article

AN - SCOPUS:0002170343

SN - 0166-218X

VL - 91

SP - 39

EP - 51

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

IS - 1-3

ER -