Generalized Ham-Sandwich Cuts |
| |
Authors: | William Steiger Jihui Zhao |
| |
Affiliation: | (2) Department of Computer Science, Lund University, Lund, Sweden |
| |
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 ≤|P i |, finds the unique hyperplane h incident with a point in each P i and having |h +∩P i |=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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|