Separable partitions

Noga Alon; Shmuel Onn

doi:10.1016/S0166-218X(98)00142-5

Separable partitions

Noga Alon
, Shmuel Onn

Research output: Contribution to journal › Article › peer-review

23 Scopus citations

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 r_p,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 r_p,d(n) = Θ(n^d(2p)) for every fixed p and d ≥ 3. and r_p,2(n) = Θ(n^6p-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.

Original language	English (US)
Pages (from-to)	39-51
Number of pages	13
Journal	Discrete Applied Mathematics
Volume	91
Issue number	1-3
DOIs	https://doi.org/10.1016/S0166-218X(98)00142-5
State	Published - 1999
Externally published	Yes

All Science Journal Classification (ASJC) codes

Discrete Mathematics and Combinatorics
Applied Mathematics

Keywords

Convex polytope
Convexity space
Davenport Schinzel sequence
Moment curve
Partition
Vapnik-Chervonenkis dimension

Access to Document

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

Cite this

@article{532955d95f5e455eaeed4aa7bea3b7bb,

title = "Separable partitions",

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(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.",

keywords = "Convex polytope, Convexity space, Davenport Schinzel sequence, Moment curve, Partition, Vapnik-Chervonenkis dimension",

author = "Noga Alon and Shmuel Onn",

note = "Funding Information: * Corresponding author. E-mail: [email protected].\textasciitilde{}l. {\textquoteright} 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.",

year = "1999",

doi = "10.1016/S0166-218X(98)00142-5",

language = "English (US)",

volume = "91",

pages = "39--51",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier B.V.",

number = "1-3",

}

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 - https://www.scopus.com/pages/publications/0002170343

UR - https://www.scopus.com/pages/publications/0002170343#tab=citedBy

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 -

Separable partitions

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this