Polynomial-time approximation schemes for piercing and covering with applications in wireless networks

详细信息	查看全文 | 推荐本文 |

• 作者：Paz Carmi ; Matthew J. Katz ; Nissan Lev-Tov
• 关键词：Geometric optimization ; Approximation algorithms ; Discrete piercing ; Covering ; Wireless networks
• 刊名：Computational Geometry
• 出版年：2008
• 期刊代码：18_09257721
• 类别：cp
• 出版时间：April 2008
• 卷：39
• 期：3
• 页码：209-218
• 文件大小：262 K

摘要

Let g src="http://www.sciencedirect.com/cache/MiamiImageURL/B6TYS-4N2KTB5-3-2/0?wchp=dGLzVlz-zSkzk" alt="Click to view the MathML source" align="absbottom" border="0" height=12 width=15> be a set of disks of arbitrary radii in the plane, and let g src="http://www.sciencedirect.com/cache/MiamiImageURL/B6TYS-4N2KTB5-3-F/0?wchp=dGLzVlz-zSkzk" alt="Click to view the MathML source" align="absbottom" border="0" height=13 width=14> be a set of points. We study the following three problems: (i) Assuming g src="http://www.sciencedirect.com/cache/MiamiImageURL/B6TYS-4N2KTB5-3-T/0?wchp=dGLzVlz-zSkzk" alt="Click to view the MathML source" align="absbottom" border="0" height=13 width=14> contains the set of center points of disks in g src="http://www.sciencedirect.com/cache/MiamiImageURL/B6TYS-4N2KTB5-3-V/0?wchp=dGLzVlz-zSkzk" alt="Click to view the MathML source" align="absbottom" border="0" height=12 width=15>, find a minimum-cardinality subset g src="http://www.sciencedirect.com/cache/MiamiImageURL/B6TYS-4N2KTB5-3-W/0?wchp=dGLzVlz-zSkzk" alt="Click to view the MathML source" align="absbottom" border="0" height=13 width=20> of g src="http://www.sciencedirect.com/cache/MiamiImageURL/B6TYS-4N2KTB5-3-X/0?wchp=dGLzVlz-zSkzk" alt="Click to view the MathML source" align="absbottom" border="0" height=13 width=14> (if exists), such that each disk in g src="http://www.sciencedirect.com/cache/MiamiImageURL/B6TYS-4N2KTB5-3-Y/0?wchp=dGLzVlz-zSkzk" alt="Click to view the MathML source" align="absbottom" border="0" height=12 width=15> is pierced by at least h points of g src="http://www.sciencedirect.com/cache/MiamiImageURL/B6TYS-4N2KTB5-3-10/0?wchp=dGLzVlz-zSkzk" alt="Click to view the MathML source" align="absbottom" border="0" height=13 width=20>, where h is a given constant. We call this problem minimum h-piercing. (ii) Assuming g src="http://www.sciencedirect.com/cache/MiamiImageURL/B6TYS-4N2KTB5-3-11/0?wchp=dGLzVlz-zSkzk" alt="Click to view the MathML source" align="absbottom" border="0" height=13 width=14> is such that for each g src="http://www.sciencedirect.com/cache/MiamiImageURL/B6TYS-4N2KTB5-3-3/0?wchp=dGLzVlz-zSkzk" alt="Click to view the MathML source" align="absbottom" border="0" height=12 width=44> there exists a point in g src="http://www.sciencedirect.com/cache/MiamiImageURL/B6TYS-4N2KTB5-3-4/0?wchp=dGLzVlz-zSkzk" alt="Click to view the MathML source" align="absbottom" border="0" height=13 width=14> whose distance from D's center is at most αr(D), where r(D) is D's radius and 0g src="http://www.sciencedirect.com/scidirimg/entities/2a7d.gif" alt="less-than-or-equals, slant" border=0>α<1 is a given constant, find a minimum-cardinality subset g src="http://www.sciencedirect.com/cache/MiamiImageURL/B6TYS-4N2KTB5-3-8/0?wchp=dGLzVlz-zSkzk" alt="Click to view the MathML source" align="absbottom" border="0" height=13 width=20> of g src="http://www.sciencedirect.com/cache/MiamiImageURL/B6TYS-4N2KTB5-3-9/0?wchp=dGLzVlz-zSkzk" alt="Click to view the MathML source" align="absbottom" border="0" height=13 width=14>, such that each disk in g src="http://www.sciencedirect.com/cache/MiamiImageURL/B6TYS-4N2KTB5-3-B/0?wchp=dGLzVlz-zSkzk" alt="Click to view the MathML source" align="absbottom" border="0" height=12 width=15> is pierced by at least one point of g src="http://www.sciencedirect.com/cache/MiamiImageURL/B6TYS-4N2KTB5-3-C/0?wchp=dGLzVlz-zSkzk" alt="Click to view the MathML source" align="absbottom" border="0" height=13 width=20>. We call this problem minimum discrete piercing with cores. (iii) Assuming g src="http://www.sciencedirect.com/cache/MiamiImageURL/B6TYS-4N2KTB5-3-D/0?wchp=dGLzVlz-zSkzk" alt="Click to view the MathML source" align="absbottom" border="0" height=13 width=14> is the set of center points of disks in g src="http://www.sciencedirect.com/cache/MiamiImageURL/B6TYS-4N2KTB5-3-G/0?wchp=dGLzVlz-zSkzk" alt="Click to view the MathML source" align="absbottom" border="0" height=12 width=15>, and that each g src="http://www.sciencedirect.com/cache/MiamiImageURL/B6TYS-4N2KTB5-3-H/0?wchp=dGLzVlz-zSkzk" alt="Click to view the MathML source" align="absbottom" border="0" height=12 width=44> covers at most l points of g src="http://www.sciencedirect.com/cache/MiamiImageURL/B6TYS-4N2KTB5-3-J/0?wchp=dGLzVlz-zSkzk" alt="Click to view the MathML source" align="absbottom" border="0" height=13 width=14>, where l is a constant, find a minimum-cardinality subset g src="http://www.sciencedirect.com/cache/MiamiImageURL/B6TYS-4N2KTB5-3-K/0?wchp=dGLzVlz-zSkzk" alt="Click to view the MathML source" align="absbottom" border="0" height=12 width=21> of g src="http://www.sciencedirect.com/cache/MiamiImageURL/B6TYS-4N2KTB5-3-M/0?wchp=dGLzVlz-zSkzk" alt="Click to view the MathML source" align="absbottom" border="0" height=12 width=15>, such that each point of g src="http://www.sciencedirect.com/cache/MiamiImageURL/B6TYS-4N2KTB5-3-N/0?wchp=dGLzVlz-zSkzk" alt="Click to view the MathML source" align="absbottom" border="0" height=13 width=14> is covered by at least one disk of g src="http://www.sciencedirect.com/cache/MiamiImageURL/B6TYS-4N2KTB5-3-P/0?wchp=dGLzVlz-zSkzk" alt="Click to view the MathML source" align="absbottom" border="0" height=12 width=21>. We call this problem minimum center covering. For each of these problems we present a constant-factor approximation algorithm (trivial for problem (iii)), followed by a polynomial-time approximation scheme. The polynomial-time approximation schemes are based on an adapted and extended version of Chan's [T.M. Chan, Polynomial-time approximation schemes for packing and piercing fat objects, J. Algorithms 46 (2003) 178–189] separator theorem. Our PTAS for problem (ii) enables one, in practical cases, to obtain a (1+ε)-approximation for minimum discrete piercing (i.e., for arbitrary g src="http://www.sciencedirect.com/cache/MiamiImageURL/B6TYS-4N2KTB5-3-S/0?wchp=dGLzVlz-zSkzk" alt="Click to view the MathML source" align="absbottom" border="0" height=13 width=14>).