期刊
INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS
卷 22, 期 5, 页码 407-419出版社
WORLD SCIENTIFIC PUBL CO PTE LTD
DOI: 10.1142/S0218195912500094
关键词
Discrete unit disk cover; geometric set cover; approximation algorithms
资金
- Natural Sciences and Engineering Research Council of Canada (NSERC)
- NSERC
Given a set P of n points and a set D of m unit disks on a 2-dimensional plane, the discrete unit disk cover (DUDC) problem is (i) to check whether each point in P is covered by at least one disk in D or not and (ii) if so, then find a minimum cardinality subset D* subset of D such that the unit disks in D* cover all the points in P. 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 c log vertical bar P vertical bar, 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 O(n log n + m log m + m n). The previous best known tractable solution for the same problem was a 22-factor approximation algorithm with running time O(m(2)n(4)).
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据