---
_id: '4106'
abstract:
- lang: eng
text: 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.
article_processing_charge: No
article_type: original
author:
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Roman
full_name: Waupotitsch, Roman
last_name: Waupotitsch
citation:
ama: 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
apa: 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
chicago: 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.
ieee: 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.
ista: Edelsbrunner H, Waupotitsch R. 1986. Computing a ham-sandwich cut in two dimensions.
Journal of Symbolic Computation. 2(2), 171–178.
mla: 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.
short: H. Edelsbrunner, R. Waupotitsch, Journal of Symbolic Computation 2 (1986)
171–178.
date_created: 2018-12-11T12:06:58Z
date_published: 1986-01-01T00:00:00Z
date_updated: 2022-02-01T11:22:59Z
day: '01'
doi: 10.1016/S0747-7171(86)80020-7
extern: '1'
intvolume: ' 2'
issue: '2'
language:
- iso: eng
month: '01'
oa_version: None
page: 171 - 178
publication: Journal of Symbolic Computation
publication_identifier:
eissn:
- 1095-855X
issn:
- 0747-7171
publication_status: published
publisher: Elsevier
publist_id: '2018'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Computing a ham-sandwich cut in two dimensions
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 2
year: '1986'
...