Computing generalized ham-sandwich cuts

作者：Bereg Sergey^*

来源：Information Processing Letters, 2012, 112(13): 532-534.

DOI：10.1016/j.ipl.2012.03.013

• Computational geometry
• Ham-sandwich theorem

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 %26gt;= 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.

• 出版日期2012-7-15