Computing a ham-sandwich cut in two dimensions Journal Article


Author(s): Edelsbrunner, Herbert; Waupotitsch, Roman
Article Title: Computing a ham-sandwich cut in two dimensions
Affiliation
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.
Journal Title: Journal of Symbolic Computation
Volume: 2
Issue 2
ISSN: 0747-7171
Publisher: Elsevier  
Date Published: 1986-01-01
Start Page: 171
End Page: 178
DOI: 10.1016/S0747-7171(86)80020-7
Open access: no
IST Austria Authors