Separable partitions

Noga Alon, Shmuel Onn

Research output: Contribution to journalArticlepeer-review

23 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)39-51
Number of pages13
JournalDiscrete Applied Mathematics
Issue number1-3
StatePublished - 1999
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics


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


Dive into the research topics of 'Separable partitions'. Together they form a unique fingerprint.

Cite this