Separable partitions

Noga Alon, Shmuel Onn

Research output: Contribution to journalArticle

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 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
Volume91
Issue number1-3
DOIs
StatePublished - Jan 1 1999
Externally publishedYes

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

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

  • Cite this