## Abstract

Bárány, Hubard, and Jerónimo recently showed that for given well-separated convex bodies S_{1},..., S_{d} in R^{d} and constants β_{i}∈[0,1], there exists a unique hyperplane h with the property that Vol (h^{+}∩S_{i})=β_{i}·Vol (S_{i}); h^{+} is the closed positive transversal halfspace of h, and h is a "generalized ham-sandwich cut." We give a discrete analogue for a set S of n points in R^{d} which are partitioned into a family S=P_{1}∪···∪P_{d} of well-separated sets and are in weak general position. The combinatorial proof inspires an O(n(log n)^{d-3}) algorithm which, given positive integers a_{i}≤{pipe}P_{i}{pipe}, finds the unique hyperplane h incident with a point in each P_{i} and having {pipe}h^{+}∩P_{i}{pipe}=a_{i}. Finally we show two other consequences of the direct combinatorial proof: the first is a stronger result, namely that in the discrete case, the conditions assuring existence and uniqueness of generalized cuts are also necessary; the second is an alternative and simpler proof of the theorem in Bárány et al., and in addition, we strengthen the result via a partial converse.

Original language | English (US) |
---|---|

Pages (from-to) | 535-545 |

Number of pages | 11 |

Journal | Discrete and Computational Geometry |

Volume | 44 |

Issue number | 3 |

DOIs | |

State | Published - 2010 |

## All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics

## Keywords

- Algorithms
- Ham-sandwich cuts
- Partitions of measures