### 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 | |

State | Published - Jan 1 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

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

## Cite this

Alon, N., & Onn, S. (1999). Separable partitions.

*Discrete Applied Mathematics*,*91*(1-3), 39-51. https://doi.org/10.1016/S0166-218X(98)00142-5