Computing a face in an arrangement of line segments

Bernard Chazelle; Herbert Edelsbrunner; Leonidas Guibas; Micha Sharir; Jack Snoeyink

Computing a face in an arrangement of line segments

Bernard Chazelle, Herbert Edelsbrunner, Leonidas Guibas, Micha Sharir, Jack Snoeyink

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

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 [3].

Original language	English (US)
Title of host publication	Proceedings of the 2nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1991
Publisher	Association for Computing Machinery
Pages	441-448
Number of pages	8
ISBN (Print)	0897913760
State	Published - Mar 1 1991
Event	2nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1991 - San Francisco, United States Duration: Jan 28 1991 → Jan 30 1991

Publication series

Name	Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Other

Other	2nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1991
Country/Territory	United States
City	San Francisco
Period	1/28/91 → 1/30/91

All Science Journal Classification (ASJC) codes

Software
Mathematics(all)

Cite this

@inproceedings{2c07e99f5291419badc2595ed52f8d7d,

title = "Computing a face in an arrangement of line segments",

abstract = "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 [3].",

author = "Bernard Chazelle and Herbert Edelsbrunner and Leonidas Guibas and Micha Sharir and Jack Snoeyink",

note = "Funding Information: ~rk by Bernard Char,elle has been supported by NSF Grant CCR-87-00917. Work by Herbert Edelsbrurmer has been SUP ported by NSF Grant CC R-89-21421. Work by Micha Sharir h-been supported by ONR Grants NOO014-89-J-3042 and NOOOl& 90J-1284, by NSF Grant CCIL89-01484, and by grants from the U.S .-IsraeL Binational Science Foundation, the Fund for Basic Research administered by the Israeli Academy of Sciences, and the G .I.F., the German-Israeli Foundation for Scientific Research and Development. t Computer Science Department, t Computer Science Department, Urbana-Champaign Publisher Copyright: {\textcopyright} 1991 Association for Computing Machinery. All rights reserved.; 2nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1991 ; Conference date: 28-01-1991 Through 30-01-1991",

year = "1991",

month = mar,

day = "1",

language = "English (US)",

isbn = "0897913760",

series = "Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms",

publisher = "Association for Computing Machinery",

pages = "441--448",

booktitle = "Proceedings of the 2nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1991",

}

Chazelle, B, Edelsbrunner, H, Guibas, L, Sharir, M & Snoeyink, J 1991, Computing a face in an arrangement of line segments. in Proceedings of the 2nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1991. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, Association for Computing Machinery, pp. 441-448, 2nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1991, San Francisco, United States, 1/28/91.

Computing a face in an arrangement of line segments. / Chazelle, Bernard; Edelsbrunner, Herbert; Guibas, Leonidas et al.

Proceedings of the 2nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1991. Association for Computing Machinery, 1991. p. 441-448 (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Computing a face in an arrangement of line segments

AU - Chazelle, Bernard

AU - Edelsbrunner, Herbert

AU - Guibas, Leonidas

AU - Sharir, Micha

AU - Snoeyink, Jack

N1 - Funding Information: ~rk by Bernard Char,elle has been supported by NSF Grant CCR-87-00917. Work by Herbert Edelsbrurmer has been SUP ported by NSF Grant CC R-89-21421. Work by Micha Sharir h-been supported by ONR Grants NOO014-89-J-3042 and NOOOl& 90J-1284, by NSF Grant CCIL89-01484, and by grants from the U.S .-IsraeL Binational Science Foundation, the Fund for Basic Research administered by the Israeli Academy of Sciences, and the G .I.F., the German-Israeli Foundation for Scientific Research and Development. t Computer Science Department, t Computer Science Department, Urbana-Champaign Publisher Copyright: © 1991 Association for Computing Machinery. All rights reserved.

PY - 1991/3/1

Y1 - 1991/3/1

N2 - 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 [3].

AB - 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 [3].

UR - http://www.scopus.com/inward/record.url?scp=84914756148&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84914756148&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:84914756148

SN - 0897913760

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 441

EP - 448

BT - Proceedings of the 2nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1991

PB - Association for Computing Machinery

T2 - 2nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1991

Y2 - 28 January 1991 through 30 January 1991

ER -

Computing a face in an arrangement of line segments

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Other files and links

Fingerprint

Cite this