{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,9]],"date-time":"2026-05-09T17:28:34Z","timestamp":1778347714224,"version":"3.51.4"},"reference-count":14,"publisher":"World Scientific Pub Co Pte Lt","issue":"05","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[2012,10]]},"abstract":"<jats:p> Given a set [Formula: see text] of n points and a set [Formula: see text] of m unit disks on a 2-dimensional plane, the discrete unit disk cover (DUDC) problem is (i) to check whether each point in [Formula: see text] is covered by at least one disk in [Formula: see text] or not and (ii) if so, then find a minimum cardinality subset [Formula: see text] such that the unit disks in [Formula: see text] cover all the points in [Formula: see text]. The discrete unit disk cover problem is a geometric version of the general set cover problem which is NP-hard. The general set cover problem is not approximable within [Formula: see text], for some constant c, but the DUDC problem was shown to admit a constant factor approximation. In this paper, we provide an algorithm with constant approximation factor 18. The running time of the proposed algorithm is [Formula: see text]. The previous best known tractable solution for the same problem was a 22-factor approximation algorithm with running time [Formula: see text]. <\/jats:p>","DOI":"10.1142\/s0218195912500094","type":"journal-article","created":{"date-parts":[[2013,2,19]],"date-time":"2013-02-19T17:43:31Z","timestamp":1361295811000},"page":"407-419","source":"Crossref","is-referenced-by-count":33,"title":["ON THE DISCRETE UNIT DISK COVER PROBLEM"],"prefix":"10.1142","volume":"22","author":[{"given":"GAUTAM K.","family":"DAS","sequence":"first","affiliation":[{"name":"Department of Mathematics, Indian Institute of Technology Guwahati, Guwahati 781 039, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"ROBERT","family":"FRASER","sequence":"additional","affiliation":[{"name":"David R. Cheriton School of Computer Science, University of Waterloo, 200 University Ave. West, Waterloo, Ontario, N2L3G1, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"ALEJANDRO","family":"L\u00d3OPEZ-ORTIZ","sequence":"additional","affiliation":[{"name":"David R. Cheriton School of Computer Science, University of Waterloo, 200 University Ave. West, Waterloo, Ontario, N2L3G1, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"BRADFORD G.","family":"NICKERSON","sequence":"additional","affiliation":[{"name":"Faculty of Computer Science, University of New Brunswick, P. O. Box 4400, 540 Windsor Street, Fredericton, New Brunswick, E3B 5A3, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2013,2,19]]},"reference":[{"key":"p_7","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0110-y"},{"key":"p_8","doi-asserted-by":"publisher","DOI":"10.1145\/299917.299918"},{"key":"p_10","doi-asserted-by":"publisher","DOI":"10.1007\/BF02570718"},{"key":"p_11","doi-asserted-by":"publisher","DOI":"10.1142\/S1793830910000486"},{"key":"p_12","doi-asserted-by":"publisher","DOI":"10.1023\/B:MONE.0000013622.63511.57"},{"key":"p_13","first-page":"644","volume":"4835","author":"Carmi P.","year":"2007","journal-title":"LNCS -"},{"key":"p_14","doi-asserted-by":"publisher","DOI":"10.1287\/moor.4.3.233"},{"key":"p_15","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(81)90111-3"},{"key":"p_16","doi-asserted-by":"publisher","DOI":"10.1137\/0216064"},{"key":"p_17","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(91)90075-S"},{"key":"p_18","doi-asserted-by":"publisher","DOI":"10.1145\/2455.214106"},{"key":"p_19","doi-asserted-by":"publisher","DOI":"10.1007\/BF01228511"},{"key":"p_20","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(82)90018-9"},{"key":"p_22","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-010-9285-9"}],"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218195912500094","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T16:11:54Z","timestamp":1565194314000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218195912500094"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,10]]},"references-count":14,"journal-issue":{"issue":"05","published-online":{"date-parts":[[2013,2,19]]},"published-print":{"date-parts":[[2012,10]]}},"alternative-id":["10.1142\/S0218195912500094"],"URL":"https:\/\/doi.org\/10.1142\/s0218195912500094","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"value":"0218-1959","type":"print"},{"value":"1793-6357","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,10]]}}}