{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,9]],"date-time":"2023-01-09T19:50:47Z","timestamp":1673293847165},"reference-count":11,"publisher":"World Scientific Pub Co Pte Lt","issue":"02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[1998,4]]},"abstract":"<jats:p> We describe a robust, dynamic algorithm to compute the arrangement of a set of line segments in the plane, and its implementation. The algorithm is robust because, following Greene<jats:sup>7<\/jats:sup> and Hobby,<jats:sup>11<\/jats:sup> it rounds the endpoints and intersections of all line segments to representable points, but in a way that is globally topologically consistent. The algorithm is dynamic because, following Mulmuley,<jats:sup>16<\/jats:sup> it uses a randomized hierarchy of vertical cell decompositions to make locating points, and inserting and deleting line segments, efficient. Our algorithm is novel because it marries the robustness of the Greene and Hobby algorithms with Mulmuley's dynamic algorithm in a way that preserves the desirable properties of each. <\/jats:p>","DOI":"10.1142\/s0218195998000096","type":"journal-article","created":{"date-parts":[[2003,7,22]],"date-time":"2003-07-22T11:10:21Z","timestamp":1058872221000},"page":"157-178","source":"Crossref","is-referenced-by-count":12,"title":["Rounding Arrangements Dynamically"],"prefix":"10.1142","volume":"08","author":[{"given":"Leonidas J.","family":"Guibas","sequence":"first","affiliation":[{"name":"Computer Science Department, Stanford University, Stanford, California 94305, USA"}]},{"given":"David H.","family":"Marimont","sequence":"additional","affiliation":[{"name":"Xerox Palo Alto Research Center, 3333 Coyote Hill Road, Palo Alto, California 94304, USA"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"p_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1979.1675432"},{"key":"p_2","doi-asserted-by":"publisher","DOI":"10.1145\/147508.147511"},{"key":"p_3","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187740"},{"key":"p_4","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63524"},{"key":"p_5","doi-asserted-by":"publisher","DOI":"10.1145\/109648.109685"},{"key":"p_6","doi-asserted-by":"publisher","DOI":"10.1145\/262839.262985"},{"key":"p_8","first-page":"143","author":"Greene D. H.","year":"1986","journal-title":"Proc. 27th Ann. Symp. on Foundations of Computer Science"},{"key":"p_9","doi-asserted-by":"publisher","DOI":"10.1145\/220279.220300"},{"key":"p_10","first-page":"208","author":"Guibas L. J.","year":"1989","journal-title":"Proc. Fifth Ann. Symp. on Computational Geometry"},{"key":"p_15","first-page":"55","author":"Milenkovic V.","year":"1995","journal-title":"Proceedings of the 7th Canadian Computational Geometry Conference"},{"key":"p_16","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(08)80064-8"}],"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218195998000096","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T00:31:36Z","timestamp":1565137896000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218195998000096"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,4]]},"references-count":11,"journal-issue":{"issue":"02","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[1998,4]]}},"alternative-id":["10.1142\/S0218195998000096"],"URL":"https:\/\/doi.org\/10.1142\/s0218195998000096","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"value":"0218-1959","type":"print"},{"value":"1793-6357","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,4]]}}}