{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T14:45:48Z","timestamp":1787496348331,"version":"build-2736575974"},"reference-count":12,"publisher":"World Scientific Pub Co Pte Ltd","issue":"03","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[2009,6]]},"abstract":"<jats:p>We consider the following packing problem. Let \u03b1 be a fixed real in (0, 1]. We are given a bounding rectangle \u03c1 and a set [Formula: see text] of n possibly intersecting unit disks whose centers lie in \u03c1. The task is to pack a set [Formula: see text] of m disjoint disks of radius \u03b1 into \u03c1 such that no disk in B intersects a disk in [Formula: see text], where m is the maximum number of unit disks that can be packed. In this paper we present a polynomial-time algorithm for \u03b1 = 2\/3. So far only the case of packing squares has been considered. For that case, Baur and Fekete have given a polynomial-time algorithm for \u03b1 = 2\/3 and have shown that the problem cannot be solved in polynomial time for any \u03b1 &gt; 13\/14 unless [Formula: see text].<\/jats:p>","DOI":"10.1142\/s0218195909002952","type":"journal-article","created":{"date-parts":[[2009,6,24]],"date-time":"2009-06-24T22:31:29Z","timestamp":1245882689000},"page":"267-288","source":"Crossref","is-referenced-by-count":7,"title":["A POLYNOMIAL-TIME APPROXIMATION ALGORITHM FOR A GEOMETRIC DISPERSION PROBLEM"],"prefix":"10.1142","volume":"19","author":[{"given":"MARC","family":"BENKERT","sequence":"first","affiliation":[{"name":"XP Software, 8-10 Purdue Str, Belconnen, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"JOACHIM","family":"GUDMUNDSSON","sequence":"additional","affiliation":[{"name":"National ICT Australia Ltd, Sydney, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"CHRISTIAN","family":"KNAUER","sequence":"additional","affiliation":[{"name":"Institute of Computer Science, Freie Universit\u00e4t Berlin, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"REN\u00c9","family":"VAN OOSTRUM","sequence":"additional","affiliation":[{"name":"ORTEC b.v., Gouda, The Netherlands"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"ALEXANDER","family":"WOLFF","sequence":"additional","affiliation":[{"name":"Faculteit Wiskunde en Informatica, Technische Universiteit Eindhoven, The Netherlands"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(88)90035-1"},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1016\/0031-3203(84)90064-5"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0022-x"},{"key":"rf4","volume-title":"Research Problems in Discrete Geometry","author":"Brass P.","year":"2005"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(81)90111-3"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1145\/2455.214106"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(93)90033-3"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1287\/opre.42.2.299"},{"key":"rf12","volume-title":"Packing and Covering","author":"Ambrose Rogers C.","year":"1964"},{"key":"rf14","doi-asserted-by":"crossref","unstructured":"G.\u00a0Fejes T\u00f3th, Handbook of Discrete and Computational Geometry, eds. J. E.\u00a0Goodman and J.\u00a0O'Rourke (CRC Press, 2004)\u00a0pp. 19\u201341.","DOI":"10.1201\/9781420035315"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(88)90174-3"},{"key":"rf16","volume-title":"Sphere Packings","author":"Zong C.","year":"1999"}],"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218195909002952","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,19]],"date-time":"2020-05-19T20:34:11Z","timestamp":1589920451000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218195909002952"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,6]]},"references-count":12,"journal-issue":{"issue":"03","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2009,6]]}},"alternative-id":["10.1142\/S0218195909002952"],"URL":"https:\/\/doi.org\/10.1142\/s0218195909002952","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"value":"0218-1959","type":"print"},{"value":"1793-6357","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,6]]}}}