Computing a ham-sandwich cut in two dimensions

H. Edelsbrunner, R. Waupotitsch, Journal of Symbolic Computation 2 (1986) 171–178.

Download
No fulltext has been uploaded. References only!

Journal Article | Published
Author
;
Abstract
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
Volume
2
Issue
2
Page
171 - 178
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, 2(2), 171–178. 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 2, no. 2 (1986): 171–78. 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, 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.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar