---
_id: '4036'
abstract:
- lang: eng
  text: This paper presents 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 [in Discrete Comput. Geom., 4(1989), pp. 387-421]. A few extensions
    of the technique, obtaining efficient randomized incremental algorithms for constructing
    the entire arrangement of a collection of line segments and for computing a single
    face in an arrangement of Jordan arcs are also presented.
acknowledgement: 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
article_type: original
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 and related problems. <i>SIAM Journal on Computing</i>.
    1993;22(6):1286-1302. doi:<a href="https://doi.org/10.1137/0222077 ">10.1137/0222077
    </a>
  apa: Chazelle, B., Edelsbrunner, H., Guibas, L., Sharir, M., &#38; Snoeyink, J.
    (1993). Computing a face in an arrangement of line segments and related problems.
    <i>SIAM Journal on Computing</i>. SIAM. <a href="https://doi.org/10.1137/0222077
    ">https://doi.org/10.1137/0222077 </a>
  chicago: Chazelle, Bernard, Herbert Edelsbrunner, Leonidas Guibas, Micha Sharir,
    and Jack Snoeyink. “Computing a Face in an Arrangement of Line Segments and Related
    Problems.” <i>SIAM Journal on Computing</i>. SIAM, 1993. <a href="https://doi.org/10.1137/0222077
    ">https://doi.org/10.1137/0222077 </a>.
  ieee: B. Chazelle, H. Edelsbrunner, L. Guibas, M. Sharir, and J. Snoeyink, “Computing
    a face in an arrangement of line segments and related problems,” <i>SIAM Journal
    on Computing</i>, vol. 22, no. 6. SIAM, pp. 1286–1302, 1993.
  ista: Chazelle B, Edelsbrunner H, Guibas L, Sharir M, Snoeyink J. 1993. Computing
    a face in an arrangement of line segments and related problems. SIAM Journal on
    Computing. 22(6), 1286–1302.
  mla: Chazelle, Bernard, et al. “Computing a Face in an Arrangement of Line Segments
    and Related Problems.” <i>SIAM Journal on Computing</i>, vol. 22, no. 6, SIAM,
    1993, pp. 1286–302, doi:<a href="https://doi.org/10.1137/0222077 ">10.1137/0222077
    </a>.
  short: B. Chazelle, H. Edelsbrunner, L. Guibas, M. Sharir, J. Snoeyink, SIAM Journal
    on Computing 22 (1993) 1286–1302.
date_created: 2018-12-11T12:06:34Z
date_published: 1993-12-01T00:00:00Z
date_updated: 2022-03-30T08:07:21Z
day: '01'
doi: '10.1137/0222077 '
extern: '1'
intvolume: '        22'
issue: '6'
language:
- iso: eng
main_file_link:
- url: https://epubs.siam.org/doi/10.1137/0222077
month: '12'
oa_version: None
page: 1286 - 1302
publication: SIAM Journal on Computing
publication_identifier:
  issn:
  - 0097-5397
publication_status: published
publisher: SIAM
publist_id: '2087'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Computing a face in an arrangement of line segments and related problems
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 22
year: '1993'
...