论文标题
用单位正方形的最低点覆盖点
Minimum Ply Covering of Points with Unit Squares
论文作者
论文摘要
鉴于欧几里得飞机中的轴平行单位平方的一组$ p $和一套$ u $ $ u $，带有$ u $ $ u $的$ p $的最低覆盖率是$ u $的子集，$ u $的子集涵盖$ p $，并最大程度地减少了共享一个共享的平方数量，称为共同的互动，称为最低$ P $与$ u $ $ u $ $ $ $ $。 Biedl等。 [计算。 GEOM。，94：101712，2020]表明，通过一组轴平行单位正方形确定一组点的最小覆盖码为NP- hard，并给出了一个多项式时间2-辅助算法的实例，最小封面盖的最小封面数为恒定。当最小覆盖号为$ω（1）$时，是否存在多项式近似算法存在问题。我们解决这个开放的问题，并提出一个多项式$（8+ \ varepsilon）$ - 对于总体问题的近似算法，对于每个固定的$ \ varepsilon> 0 $。
Given a set $P$ of points and a set $U$ of axis-parallel unit squares in the Euclidean plane, a minimum ply cover of $P$ with $U$ is a subset of $U$ that covers $P$ and minimizes the number of squares that share a common intersection, called the minimum ply cover number of $P$ with $U$. Biedl et al. [Comput. Geom., 94:101712, 2020] showed that determining the minimum ply cover number for a set of points by a set of axis-parallel unit squares is NP-hard, and gave a polynomial-time 2-approximation algorithm for instances in which the minimum ply cover number is constant. The question of whether there exists a polynomial-time approximation algorithm remained open when the minimum ply cover number is $ω(1)$. We settle this open question and present a polynomial-time $(8+\varepsilon)$-approximation algorithm for the general problem, for every fixed $\varepsilon>0$.
