A polynomial-time approximation scheme for the geometric unique coverage problem on unit squares

详细信息    查看全文

• 作者：Takehiro Ito^a ; ^{takehiro@ecei.tohoku.ac.jp" class="auth_mail" title="E-mail the corresponding author} ; Shin-ichi Nakano^b ; ^{nakano@cs.gunma-u.ac.jp" class="auth_mail" title="E-mail the corresponding author} ; Yoshio Okamoto^c ; ^{okamotoy@uec.ac.jp" class="auth_mail" title="E-mail the corresponding author} ; Yota Otachi^d ; ^{otachi@jaist.ac.jp" class="auth_mail" title="E-mail the corresponding author} ; Ryuhei Uehara^d ; ^{uehara@jaist.ac.jp" class="auth_mail" title="E-mail the corresponding author} ; Takeaki Uno^e ; ^{uno@nii.ac.jp" class="auth_mail" title="E-mail the corresponding author} ; Yushi Uno^f ; ^{uno@mi.s.osakafu-u.ac.jp" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Polynomial-time approximation scheme ; Unique coverage problem ; Dynamic programming ; Shifting strategy
• 刊名：Computational Geometry
• 出版年：2016
• 出版时间：January 2016
• 年：2016
• 卷：51
• 期：Complete
• 页码：25-39
• 全文大小：512 K

文摘

We give a polynomial-time approximation scheme for the unique unit-square coverage problem: given a set of points and a set of axis-parallel unit squares, both in the plane, we wish to find a subset of squares that maximizes the number of points contained in exactly one square in the subset. Erlebach and van Leeuwen [9] introduced this problem as the geometric version of the unique coverage problem, and the best approximation ratio by van Leeuwen [21] before our work was 2. Our scheme can be generalized to the budgeted unique unit-square coverage problem, in which each point has a profit, each square has a cost, and we wish to maximize the total profit of the uniquely covered points under the condition that the total cost is at most a given bound.