{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,12,19]],"date-time":"2024-12-19T01:40:24Z","timestamp":1734572424547,"version":"3.30.2"},"reference-count":18,"publisher":"World Scientific Pub Co Pte Ltd","issue":"04n05","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[2004,10]]},"abstract":"<jats:p>Given a collection [Formula: see text] of circles in the plane, we wish to construct the arrangement [Formula: see text] (namely the subdivision of the plane into vertices, edges and faces induced by [Formula: see text]) using floating point arithmetic. We present an efficient scheme, controlled perturbation, that perturbs the circles in [Formula: see text] slightly to form a collection [Formula: see text], so that all the predicates that arise in the construction of [Formula: see text] are computed accurately and [Formula: see text] is degeneracy free.<\/jats:p><jats:p>We introduced controlled perturbation several years ago, and already applied it to certain types of arrangements. The major contribution of the current work is the derivation of a good (small) resolution bound, that is, a bound on the minimum separation of features of the arrangement that is required to guarantee that the predicates involved in the construction can be safely computed with the given (limited) precision arithmetic. A smaller resolution bound leads to smaller perturbation of the original input.<\/jats:p><jats:p>We present the scheme, describe how the resolution bound is determined and how it effects the perturbation magnitude. We implemented the perturbation scheme and the construction of the arrangement and we report on experimental results.<\/jats:p>","DOI":"10.1142\/s0218195904001482","type":"journal-article","created":{"date-parts":[[2004,10,15]],"date-time":"2004-10-15T09:11:35Z","timestamp":1097831495000},"page":"277-310","source":"Crossref","is-referenced-by-count":14,"title":["CONTROLLED PERTURBATION FOR ARRANGEMENTS OF CIRCLES"],"prefix":"10.1142","volume":"14","author":[{"given":"DAN","family":"HALPERIN","sequence":"first","affiliation":[{"name":"School of Computer Science, Tel Aviv University, Israel"}]},{"given":"ERAN","family":"LEISEROWITZ","sequence":"additional","affiliation":[{"name":"School of Computer Science, Tel Aviv University, Israel"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1016\/B978-044482537-7\/50003-6"},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45749-6_19"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(00)00231-6"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195901000493"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-04245-8"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(01)00050-5"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1145\/231731.231735"},{"key":"rf14","unstructured":"D.\u00a0Halperin, Handbook of Discrete and Computational Geometry, eds. J. E.\u00a0Goodman and J.\u00a0O'Rourke (CRC Press LLC, Boca Raton, FL, 1997)\u00a0pp. 389\u2013412."},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(98)00014-5"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(99)00021-8"},{"key":"rf18","doi-asserted-by":"crossref","unstructured":"V.\u00a0Karamcheti, Proc. 4th ACM Symp. Comput. Geom. (ACM Press, 1999)\u00a0pp. 351\u2013359.","DOI":"10.1145\/304893.304989"},{"key":"rf19","doi-asserted-by":"publisher","DOI":"10.1145\/99902.99905"},{"key":"rf21","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(88)90061-6"},{"key":"rf24","doi-asserted-by":"publisher","DOI":"10.1016\/B978-044482537-7\/50015-2"},{"key":"rf25","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009321"},{"key":"rf26","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45749-6_76"},{"key":"rf27","unstructured":"J. E.\u00a0Goodman and J.\u00a0O'Rourke (eds.), Handbook of Discrete and Computational Geometry (CRC Press, 1997)\u00a0pp. 653\u2013668."},{"key":"rf28","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(95)00040-2"}],"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218195904001482","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,19]],"date-time":"2024-12-19T01:02:30Z","timestamp":1734570150000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218195904001482"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,10]]},"references-count":18,"journal-issue":{"issue":"04n05","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2004,10]]}},"alternative-id":["10.1142\/S0218195904001482"],"URL":"https:\/\/doi.org\/10.1142\/s0218195904001482","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"type":"print","value":"0218-1959"},{"type":"electronic","value":"1793-6357"}],"subject":[],"published":{"date-parts":[[2004,10]]}}}