A polynomial-time approximation scheme for the geometric unique coverage problem on unit squares (Q902421): Difference between revisions

The authors present a polynomial-time approximation scheme for the unit-square coverage problem. More precisely, if a set of points and a set of axis-parallel unique squares in the plane are given, then the authors want to find a subset of squares that maximizes the number of points contained in exactly one square in the subset. The problem is interesting and has been introduced by \textit{T. Erlebach} and \textit{E. J. van Leeuwen} [New York, NY: Association for Computing Machinery (ACM); Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM), 1267--1276 (2008; Zbl 1192.68743)] in the geometric version of the unique coverage problem. The paper consists of six parts. New results are established and in conclusion, the paper is well written and structured.