Computing generalized ham-sandwich cuts
Barany et al. (2008) [1] proved that, for any beta is an element of [0,1](d) and any d well-separated convex bodies S-1, S-2, ... S-d in R-d, there exists a hyperplane (a generalized ham-sandwich cut) splitting the volume of S-i as (beta(i), 1 - beta(i)) for all i. Steiger and Zhao (2010) [4] proved a discrete analogue for n points in weak general position. The (elegant!) proof inspired an algorithm for computing this hyperplane (Steiger and Zhao, 2010 141) with running time O (n log(d-3) n) for d >= 3 and O(n) for d = 2. In this note we show that their algorithm can be modified to compute a generalized ham-sandwich cut in linear time for any fixed d. (C) 2012 Elsevier B.V. All rights reserved.
computational geometry ham-sandwich theorem