{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T09:10:43Z","timestamp":1787389843184,"version":"build-2736575974"},"reference-count":21,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1998,1]]},"abstract":"<jats:p>We present randomized algorithms for computing many faces in an arrangement of lines or of segments in the plane, which are considerably simpler and slightly faster than the previously known ones. The main new idea is a simple randomized $O(n \\log n)$ expected time algorithm for computing $\\sqrt{n}$ cells in an arrangement of n lines.<\/jats:p>","DOI":"10.1137\/s009753979426616x","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"491-505","source":"Crossref","is-referenced-by-count":22,"title":["Computing Many Faces in Arrangements of Lines and Segments"],"prefix":"10.1137","volume":"27","author":[{"given":"Pankaj K.","family":"Agarwal","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jir\u00ed","family":"Matousek","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Otfried","family":"Schwarzkopf","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,28]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187809"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01285815"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1007\/BF02570705"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1007\/BF02788872"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1007\/BF01377183"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1137\/0222077"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1007\/BF02122778"},{"key":"R8","unstructured":"K. Clarkson,\n                      Computing a single face in an arrangement of segments\n                      , 1990, manuscript."},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187783"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187740"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-61568-9"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187784"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(86)90078-6"},{"key":"R14","doi-asserted-by":"crossref","unstructured":"Leonidas Guibas, Micha Sharir, Combinatorics and algorithms of arrangements, Algorithms Combin., Vol. 10, Springer, Berlin, 1993, 9\u20133694g:52013","DOI":"10.1007\/978-3-642-58043-7_2"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1995.1017"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187876"},{"key":"R17","doi-asserted-by":"crossref","unstructured":"K. Mehlhorn,\n                      Data Structures and Algorithms 3: Multi\u2010dimensional Searching and Computational Geometry\n                      , Springer\u2010Verlag, Berlin, 1984.","DOI":"10.1007\/978-3-642-69900-9_2"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(08)80064-8"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1145\/102782.102785"},{"key":"R20","volume-title":"Davenport\u2010Schinzel sequences and their geometric applications","author":"Sharir Micha","year":"1995"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579194"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S009753979426616X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:12:13Z","timestamp":1787335933000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S009753979426616X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,1]]},"references-count":21,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1998,1]]}},"alternative-id":["10.1137\/S009753979426616X"],"URL":"https:\/\/doi.org\/10.1137\/s009753979426616x","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,1]]}}}