Computing a ham-sandwich cut in two dimensions
Edelsbrunner H, Waupotitsch R. 1986. Computing a ham-sandwich cut in two dimensions. Journal of Symbolic Computation. 2(2), 171–178.
Download
No fulltext has been uploaded. References only!
Journal Article
| Published
| English
Scopus indexed
Author
Edelsbrunner, HerbertISTA 
;
Waupotitsch, Roman
;
Waupotitsch, RomanAbstract
Let B be a set of nb black points and W a set of nw, white points in the Euclidean plane. A line h is said to bisect B (or W) if, at most, half of the points of B (or W) lie on any one side of h. A line that bisects both B and W is called a ham-sandwich cut of B and W. We give an algorithm that computes a ham-sandwich cut of B and W in 0((nh+nw) log (min {nb, nw}+ 1)) time. The algorithm is considerably simpler than the previous most efficient one which takes 0((nb + nw) log (nb + nw)) time.
Publishing Year
Date Published
1986-01-01
Journal Title
Journal of Symbolic Computation
Publisher
Elsevier
Volume
2
Issue
2
Page
171 - 178
ISSN
eISSN
IST-REx-ID
Cite this
Edelsbrunner H, Waupotitsch R. Computing a ham-sandwich cut in two dimensions. Journal of Symbolic Computation. 1986;2(2):171-178. doi:10.1016/S0747-7171(86)80020-7
Edelsbrunner, H., & Waupotitsch, R. (1986). Computing a ham-sandwich cut in two dimensions. Journal of Symbolic Computation. Elsevier. https://doi.org/10.1016/S0747-7171(86)80020-7
Edelsbrunner, Herbert, and Roman Waupotitsch. “Computing a Ham-Sandwich Cut in Two Dimensions.” Journal of Symbolic Computation. Elsevier, 1986. https://doi.org/10.1016/S0747-7171(86)80020-7.
H. Edelsbrunner and R. Waupotitsch, “Computing a ham-sandwich cut in two dimensions,” Journal of Symbolic Computation, vol. 2, no. 2. Elsevier, pp. 171–178, 1986.
Edelsbrunner H, Waupotitsch R. 1986. Computing a ham-sandwich cut in two dimensions. Journal of Symbolic Computation. 2(2), 171–178.
Edelsbrunner, Herbert, and Roman Waupotitsch. “Computing a Ham-Sandwich Cut in Two Dimensions.” Journal of Symbolic Computation, vol. 2, no. 2, Elsevier, 1986, pp. 171–78, doi:10.1016/S0747-7171(86)80020-7.
Google Scholar