{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,26]],"date-time":"2026-09-26T23:43:52Z","timestamp":1790466232155,"version":"4.1.0"},"reference-count":8,"publisher":"World Scientific Pub Co Pte Ltd","issue":"06","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[2011,12]]},"abstract":"<jats:p>\n                    We consider a geometric optimization problem that arises in sensor network design. Given a polygon P (possibly with holes) with n vertices, a set Y of m points representing sensors, and an integer k, 1 \u2264 k \u2264 m. The goal is to assign a sensing range, r\n                    <jats:sub>i<\/jats:sub>\n                    , to each of the sensors y\n                    <jats:sub>i<\/jats:sub>\n                    \u2208 Y, such that each point p \u2208 P is covered by at least k sensors, and the cost, [Formula: see text], of the assignment is minimized, where \u03b1 is a constant.\n                  <\/jats:p>\n                  <jats:p>\n                    In this paper, we assume that \u03b1 = 2, that is, find a set of disks centered at points of Y, such that (i) each point in P is covered by at least k disks, and (ii) the sum of the areas of the disks is minimized. We present, for any constant k \u2265 1, a polynomial-time c\n                    <jats:sub>1<\/jats:sub>\n                    -approximation algorithm for this problem, where c\n                    <jats:sub>1<\/jats:sub>\n                    = c\n                    <jats:sub>1<\/jats:sub>\n                    (k) is a constant. The discrete version, where one has to cover a given set of n points, X, by disks centered at points of Y, arises as a subproblem. We present a polynomial-time c\n                    <jats:sub>2<\/jats:sub>\n                    -approximation algorithm for this problem, where c\n                    <jats:sub>2<\/jats:sub>\n                    = c\n                    <jats:sub>2<\/jats:sub>\n                    (k) is a constant.\n                  <\/jats:p>","DOI":"10.1142\/s021819591100386x","type":"journal-article","created":{"date-parts":[[2012,2,13]],"date-time":"2012-02-13T05:01:28Z","timestamp":1329109288000},"page":"685-698","source":"Crossref","is-referenced-by-count":13,"title":["MULTI COVER OF A POLYGON MINIMIZING THE SUM OF AREAS"],"prefix":"10.1142","volume":"21","author":[{"given":"A. KARIM","family":"ABU-AFFASH","sequence":"first","affiliation":[{"name":"Department of Computer Science, Ben-Gurion University of the Negev, Beer-Sheva 84105, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"PAZ","family":"CARMI","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Ben-Gurion University of the Negev, Beer-Sheva 84105, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"MATTHEW J.","family":"KATZ","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Ben-Gurion University of the Negev, Beer-Sheva 84105, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"GILA","family":"MORGENSTERN","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Ben-Gurion University of the Negev, Beer-Sheva 84105, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"219","published-online":{"date-parts":[[2012,4,6]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795281840"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77974-2"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.07.014"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1007\/BF01377183"},{"key":"rf9","first-page":"185","volume":"7","author":"Doddi S. R.","journal-title":"Nordic. J. Comput."},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-009-9282-7"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1016\/j.comnet.2004.08.012"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1145\/185675.306789"}],"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S021819591100386X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T16:31:10Z","timestamp":1565109070000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S021819591100386X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,12]]},"references-count":8,"journal-issue":{"issue":"06","published-online":{"date-parts":[[2012,4,6]]},"published-print":{"date-parts":[[2011,12]]}},"alternative-id":["10.1142\/S021819591100386X"],"URL":"https:\/\/doi.org\/10.1142\/s021819591100386x","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"value":"0218-1959","type":"print"},{"value":"1793-6357","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,12]]}}}