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 -