Generalized Ham-Sandwich Cuts for Well Separated Point Sets
William Steiger, Jihui Zhao · 2008
Bárány, Hubard, and Jerónimo recently showed that for given well separated convex bodies S1,...,Sd in R d 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, andh is a “generalized ham-sandwich cut”. We give a discrete analogue for a set S of n points in R d which is 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 ≤|Pi|, finds the unique hyperplane h incident with a point in each Pi and having |h + ∩ Pi | = ai. Finally we show that the conditions assuring existence and uniqueness of generalized cuts are