2005-12-01
Weighted ham-sandwich cuts
Publication
Publication
Let R and B be two sets of n points. A ham-sandwich cut is a line that simultaneously bisects R and B, and is known to always exist. This notion can be generalized to the case where each point p ∈ R ∪ B is associated with a weight wp. A ham-sandwich cut can still be proved to exist, even if weights are allowed to be negative. In this paper, we present a O(n log n) algorithm to find a weighted ham-sandwich cut, but we show that deciding whether that cut is unique is 3-SUM hard.
Additional Metadata | |
---|---|
doi.org/10.1007/11589440_5 | |
Organisation | School of Computer Science |
Bose, P, & Langerman, S. (Stefan). (2005). Weighted ham-sandwich cuts. doi:10.1007/11589440_5
|