{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,3,7]],"date-time":"2024-03-07T15:51:04Z","timestamp":1709826664556},"reference-count":16,"publisher":"World Scientific Pub Co Pte Lt","issue":"06","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[2009,12]]},"abstract":" Let A and B be two sets of n resp. m disjoint unit disks in the plane, with m \u2265 n. We consider the problem of finding a translation or rigid motion of A that maximizes the total area of overlap with B. The function describing the area of overlap is quite complex, even for combinatorially equivalent translations and, hence, we turn our attention to approximation algorithms. We give deterministic (1 - \u220a)-approximation algorithms for translations and for rigid motions, which run in O((nm\/\u220a2<\/jats:sup>) log (m\/\u220a)) and O((n2<\/jats:sup>m2<\/jats:sup>\/\u220a3<\/jats:sup>) log m)) time, respectively. For rigid motions, we can also compute a (1 - \u220a)-approximation in O((m2<\/jats:sup>n4\/3<\/jats:sup>\u03941\/3<\/jats:sup>\/\u220a3<\/jats:sup>) log n log m) time, where \u0394 is the diameter of set A. Under the condition that the maximum area of overlap is at least a constant fraction of the area of A, we give a probabilistic (1 - \u220a)-approximation algorithm for rigid motions that runs in O((m2<\/jats:sup>\/\u220a4<\/jats:sup>) log 2<\/jats:sup>(m\/\u220a) log m) time and succeeds with high probability. Our results generalize to the case where A and B consist of possibly intersecting disks of different radii, provided that (i) the ratio of the radii of any two disks in A \u222a B is bounded, and (ii) within each set, the maximum number of disks with a non-empty intersection is bounded. <\/jats:p>","DOI":"10.1142\/s0218195909003118","type":"journal-article","created":{"date-parts":[[2010,1,7]],"date-time":"2010-01-07T05:22:17Z","timestamp":1262841737000},"page":"533-556","source":"Crossref","is-referenced-by-count":6,"title":["MAXIMIZING THE AREA OF OVERLAP OF TWO UNIONS OF DISKS UNDER RIGID MOTION"],"prefix":"10.1142","volume":"19","author":[{"given":"SERGIO","family":"CABELLO","sequence":"first","affiliation":[{"name":"Department of Mathematics, IMFM, and Department of Mathematics, FMF, University of Ljubljana, Jadranska 19 SI-1000 Ljubljana, Slovenia"}]},{"given":"MARK","family":"DE BERG","sequence":"additional","affiliation":[{"name":"Faculty of Mathematics and Computing Science, TU Eindhoven, P.O. Box 513, 5600 MB Eindhoven, The Netherlands"}]},{"given":"PANOS","family":"GIANNOPOULOS","sequence":"additional","affiliation":[{"name":"Institut f\u00fcr Informatik, Humbolt-Universit\u00e4t zu Berlin, Unter den Linden 6, D-10099 Berlin, Germany"}]},{"given":"CHRISTIAN","family":"KNAUER","sequence":"additional","affiliation":[{"name":"Institut f\u00fcr Informatik, Freie Universit\u00e4t Berlin, Takustra\u00dfe 9, D-14195 Berlin, Germany"}]},{"given":"REN\u00c9","family":"VAN OOSTRUM","sequence":"additional","affiliation":[{"name":"Institute of Information and Computing Sciences, Utrecht University, P.O. Box 80.089, 3508 TB Utrecht, The Netherlands"}]},{"given":"REMCO C.","family":"VELTKAMP","sequence":"additional","affiliation":[{"name":"Institute of Information and Computing Sciences, Utrecht University, P.O. Box 80.089, 3508 TB Utrecht, The Netherlands"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1994.1038"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009388"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009210"},{"key":"rf5","unstructured":"H.\u00a0Alt and L.\u00a0Guibas, Handbook of Computational Geometry, eds. J. R.\u00a0Sack and J.\u00a0Urrutia (Elsevier Science Publishers, B.V. North-Holland, Amsterdam, 1999)\u00a0pp. 121\u2013153."},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-007-1328-5"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(95)00047-X"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1007\/PL00005845"},{"key":"rf11","unstructured":"G.\u00a0Fejes T\u00f3th, Handbook of Discrete and Computational Geometry, eds. J. E.\u00a0Goodman and J.\u00a0O'Rourke (CRC Press LLC, Boca Raton, FL, 1997)\u00a0pp. 19\u201342."},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-003-1043-4"},{"key":"rf14","unstructured":"M.\u00a0Hagedoorn and R. C.\u00a0Veltkamp, Principles of Visual Information Retrieval, ed. M.\u00a0Lew (Springer, 2001)\u00a0pp. 87\u2013119."},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(98)00023-6"},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1007\/BF02189323"},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1006\/cviu.1996.0045"},{"key":"rf19","first-page":"295","volume":"1","author":"O'Rourke J.","journal-title":"IEEE Trans. Patt. Anal. Mach. Intell."},{"key":"rf20","doi-asserted-by":"publisher","DOI":"10.1111\/1467-8659.1530129"},{"key":"rf21","doi-asserted-by":"publisher","DOI":"10.1007\/BF02574706"}],"container-title":["International Journal of Computational Geometry & Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218195909003118","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T20:24:09Z","timestamp":1565123049000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218195909003118"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,12]]},"references-count":16,"journal-issue":{"issue":"06","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2009,12]]}},"alternative-id":["10.1142\/S0218195909003118"],"URL":"https:\/\/doi.org\/10.1142\/s0218195909003118","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"value":"0218-1959","type":"print"},{"value":"1793-6357","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,12]]}}}