---
_id: '4058'
abstract:
- lang: eng
  text: We present a randomized incremental algorithm for computing a single face
    in an arrangement of n line segments in the plane that is fairly simple to implement.
    The expected running time of the algorithm is O (nα(n) log n). The analysis of
    the algorithm uses a novel approach that generalizes and extends the Clarkson-Shor
    analysis technique.
acknowledgement: 'NSF Grant CC R-89-21421. The authors wish to express their gratitude
  for the generous support and hospitality of the DEC Palo Alto Systems Research Center. '
article_processing_charge: No
author:
- first_name: Bernard
  full_name: Chazelle, Bernard
  last_name: Chazelle
- first_name: Herbert
  full_name: Edelsbrunner, Herbert
  id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
  last_name: Edelsbrunner
  orcid: 0000-0002-9823-6833
- first_name: Leonidas
  full_name: Guibas, Leonidas
  last_name: Guibas
- first_name: Micha
  full_name: Sharir, Micha
  last_name: Sharir
- first_name: Jack
  full_name: Snoeyink, Jack
  last_name: Snoeyink
citation:
  ama: 'Chazelle B, Edelsbrunner H, Guibas L, Sharir M, Snoeyink J. Computing a face
    in an arrangement of line segments. In: <i>Proceedings of the 2nd Annual ACM-SIAM
    Symposium on Discrete Algorithms</i>. SIAM; 1991:441-448.'
  apa: 'Chazelle, B., Edelsbrunner, H., Guibas, L., Sharir, M., &#38; Snoeyink, J.
    (1991). Computing a face in an arrangement of line segments. In <i>Proceedings
    of the 2nd annual ACM-SIAM symposium on Discrete algorithms</i> (pp. 441–448).
    San Francisco, CA, United States of America: SIAM.'
  chicago: Chazelle, Bernard, Herbert Edelsbrunner, Leonidas Guibas, Micha Sharir,
    and Jack Snoeyink. “Computing a Face in an Arrangement of Line Segments.” In <i>Proceedings
    of the 2nd Annual ACM-SIAM Symposium on Discrete Algorithms</i>, 441–48. SIAM,
    1991.
  ieee: B. Chazelle, H. Edelsbrunner, L. Guibas, M. Sharir, and J. Snoeyink, “Computing
    a face in an arrangement of line segments,” in <i>Proceedings of the 2nd annual
    ACM-SIAM symposium on Discrete algorithms</i>, San Francisco, CA, United States
    of America, 1991, pp. 441–448.
  ista: 'Chazelle B, Edelsbrunner H, Guibas L, Sharir M, Snoeyink J. 1991. Computing
    a face in an arrangement of line segments. Proceedings of the 2nd annual ACM-SIAM
    symposium on Discrete algorithms. SODA: Symposium on Discrete Algorithms, 441–448.'
  mla: Chazelle, Bernard, et al. “Computing a Face in an Arrangement of Line Segments.”
    <i>Proceedings of the 2nd Annual ACM-SIAM Symposium on Discrete Algorithms</i>,
    SIAM, 1991, pp. 441–48.
  short: B. Chazelle, H. Edelsbrunner, L. Guibas, M. Sharir, J. Snoeyink, in:, Proceedings
    of the 2nd Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, 1991, pp. 441–448.
conference:
  end_date: 1991-01-30
  location: San Francisco, CA, United States of America
  name: 'SODA: Symposium on Discrete Algorithms'
  start_date: 1991-01-28
date_created: 2018-12-11T12:06:41Z
date_published: 1991-01-01T00:00:00Z
date_updated: 2022-02-28T14:41:47Z
day: '01'
extern: '1'
language:
- iso: eng
main_file_link:
- url: https://dl.acm.org/doi/10.5555/127787.127864
month: '01'
oa_version: None
page: 441 - 448
publication: Proceedings of the 2nd annual ACM-SIAM symposium on Discrete algorithms
publication_identifier:
  isbn:
  - 978-0-89791-376-8
publication_status: published
publisher: SIAM
publist_id: '2065'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Computing a face in an arrangement of line segments
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
year: '1991'
...