{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,24]],"date-time":"2026-04-24T21:00:47Z","timestamp":1777064447533,"version":"3.51.4"},"reference-count":12,"publisher":"World Scientific Pub Co Pte Lt","issue":"01","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Math. Algorithm. Appl."],"published-print":{"date-parts":[[2010,3]]},"abstract":"<jats:p> Given a set [Formula: see text] of m unit disks and a set [Formula: see text] of n points in the plane, the discrete unit disk cover problem is to select a minimum cardinality subset [Formula: see text] to cover [Formula: see text]. This problem is NP-hard [14] and the best previous practical solution is a 38-approximation algorithm by Carmi et al. [5]. We first consider the line-separable discrete unit disk cover problem (the set of disk centers can be separated from the set of points by a line) for which we present an O(n( log n + m))-time algorithm that finds an exact solution. Combining our line-separable algorithm with techniques from the algorithm of Carmi et al. [5] results in an O(m<jats:sup>2<\/jats:sup>n<jats:sup>4<\/jats:sup>) time 22-approximate solution to the discrete unit disk cover problem. <\/jats:p>","DOI":"10.1142\/s1793830910000486","type":"journal-article","created":{"date-parts":[[2010,4,20]],"date-time":"2010-04-20T09:35:00Z","timestamp":1271756100000},"page":"77-87","source":"Crossref","is-referenced-by-count":27,"title":["AN IMPROVED LINE-SEPARABLE ALGORITHM FOR DISCRETE UNIT DISK COVER"],"prefix":"10.1142","volume":"02","author":[{"given":"FRANCISCO","family":"CLAUDE","sequence":"first","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":"GAUTAM K.","family":"DAS","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"}]},{"given":"REZA","family":"DORRIGIV","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":"STEPHANE","family":"DUROCHER","sequence":"additional","affiliation":[{"name":"Department of Computer Science, E2-445 EITC, University of Manitoba, Winnipeg, Manitoba, R3T 2N2, Canada"}],"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\u00d3PEZ-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"}]},{"given":"ALEJANDRO","family":"SALINGER","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"}]}],"member":"219","published-online":{"date-parts":[[2012,4,5]]},"reference":[{"key":"rf1","first-page":"201","volume":"33","author":"Agarwal P.","journal-title":"Alg."},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1145\/299917.299918"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1023\/B:MONE.0000013622.63511.57"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-006-1273-8"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2009.06.005"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(81)90111-3"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1137\/0216064"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(91)90075-S"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1145\/2455.214106"},{"key":"rf13","first-page":"398","volume":"9","author":"Hwang R.","journal-title":"Alg."},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(82)90018-9"},{"key":"rf18","volume-title":"Improved results on geometric hitting set problems","author":"Mustafa N.","year":"2009"}],"container-title":["Discrete Mathematics, Algorithms and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S1793830910000486","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T01:23:13Z","timestamp":1565140993000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S1793830910000486"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,3]]},"references-count":12,"journal-issue":{"issue":"01","published-online":{"date-parts":[[2012,4,5]]},"published-print":{"date-parts":[[2010,3]]}},"alternative-id":["10.1142\/S1793830910000486"],"URL":"https:\/\/doi.org\/10.1142\/s1793830910000486","relation":{},"ISSN":["1793-8309","1793-8317"],"issn-type":[{"value":"1793-8309","type":"print"},{"value":"1793-8317","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,3]]}}}