Generalized Ham-Sandwich Cuts

William Steiger, Jihui Zhao

Research output: Contribution to journalArticlepeer-review

10 Scopus citations

Abstract

Bárány, Hubard, and Jerónimo recently showed that for given well-separated convex bodies S1,..., Sd in Rd and constants βi∈[0,1], there exists a unique hyperplane h with the property that Vol (h+∩Si)=βi·Vol (Si); 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 Rd which are partitioned into a family S=P1∪···∪Pd 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 ai≤{pipe}Pi{pipe}, finds the unique hyperplane h incident with a point in each Pi and having {pipe}h+∩Pi{pipe}=ai. 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 languageEnglish (US)
Pages (from-to)535-545
Number of pages11
JournalDiscrete and Computational Geometry
Volume44
Issue number3
DOIs
StatePublished - 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

Fingerprint

Dive into the research topics of 'Generalized Ham-Sandwich Cuts'. Together they form a unique fingerprint.

Cite this