---
_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.
    <i>Journal of Symbolic Computation</i>. 1986;2(2):171-178. doi:<a href="https://doi.org/10.1016/S0747-7171(86)80020-7">10.1016/S0747-7171(86)80020-7</a>
  apa: Edelsbrunner, H., &#38; Waupotitsch, R. (1986). Computing a ham-sandwich cut
    in two dimensions. <i>Journal of Symbolic Computation</i>. Elsevier. <a href="https://doi.org/10.1016/S0747-7171(86)80020-7">https://doi.org/10.1016/S0747-7171(86)80020-7</a>
  chicago: Edelsbrunner, Herbert, and Roman Waupotitsch. “Computing a Ham-Sandwich
    Cut in Two Dimensions.” <i>Journal of Symbolic Computation</i>. Elsevier, 1986.
    <a href="https://doi.org/10.1016/S0747-7171(86)80020-7">https://doi.org/10.1016/S0747-7171(86)80020-7</a>.
  ieee: H. Edelsbrunner and R. Waupotitsch, “Computing a ham-sandwich cut in two dimensions,”
    <i>Journal of Symbolic Computation</i>, 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.” <i>Journal of Symbolic Computation</i>, vol. 2, no. 2, Elsevier,
    1986, pp. 171–78, doi:<a href="https://doi.org/10.1016/S0747-7171(86)80020-7">10.1016/S0747-7171(86)80020-7</a>.
  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'
...