[{"quality_controlled":"1","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. ","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","publication_status":"published","abstract":[{"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.","lang":"eng"}],"main_file_link":[{"url":"https://dl.acm.org/doi/10.5555/127787.127864"}],"publist_id":"2065","language":[{"iso":"eng"}],"status":"public","type":"conference","citation":{"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.","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.","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.","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.","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.","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.","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."},"scopus_import":"1","extern":"1","author":[{"last_name":"Chazelle","full_name":"Chazelle, Bernard","first_name":"Bernard"},{"orcid":"0000-0002-9823-6833","full_name":"Edelsbrunner, Herbert","last_name":"Edelsbrunner","first_name":"Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Leonidas","last_name":"Guibas","full_name":"Guibas, Leonidas"},{"full_name":"Sharir, Micha","last_name":"Sharir","first_name":"Micha"},{"full_name":"Snoeyink, Jack","last_name":"Snoeyink","first_name":"Jack"}],"date_published":"1991-01-01T00:00:00Z","year":"1991","article_processing_charge":"No","conference":{"name":"SODA: Symposium on Discrete Algorithms","end_date":"1991-01-30","start_date":"1991-01-28","location":"San Francisco, CA, United States of America"},"date_updated":"2022-02-28T14:41:47Z","title":"Computing a face in an arrangement of line segments","publication_identifier":{"isbn":["978-0-89791-376-8"]},"month":"01","_id":"4058","publisher":"SIAM","date_created":"2018-12-11T12:06:41Z","day":"01","publication":"Proceedings of the 2nd annual ACM-SIAM symposium on Discrete algorithms","page":"441 - 448","oa_version":"None"}]