Covering points by disjoint boxes with outliers. (English) Zbl 1217.68109
Summary: For a set of \(n\) points in the plane, we consider the axis-aligned \((p,k)\)-Box Covering problem: Find \(p\) axis-aligned, pairwise-disjoint boxes that together contain at least \(n-k\) points. In this paper, we consider the boxes to be either squares or rectangles, and we want to minimize the area of the largest box. For general \(p\) we show that the problem is NP-hard for both squares and rectangles. For a small, fixed number \(p\), we give algorithms that find the solution in the following running times: For squares we have \(O(n+k\log k)\) time for \(p=1\), and \(O(n\log n+k^p\log^p k)\) time for \(p=2,3\). For rectangles we get \(O(n+k^3)\) for \(p=1\) and \(O(n\log n+k^{2+p}\log^{p-1} k)\) for \(p=2,3\). In all cases, our algorithms use \(O(n)\) space.
MSC:
| 68Q25 | Analysis of algorithms and problem complexity |
| 52B55 | Computational aspects related to convexity |
| 52C22 | Tilings in \(n\) dimensions (aspects of discrete geometry) |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
Keywords:
NP-hard; optimization; outliers; rectangle covering; square covering; rectilinear \(p\)-center problemReferences:
| [1] | Aggarwal, A.; Imai, H.; Katoh, N.; Suri, S., Finding \(k\) points with minimum diameter and related problems, J. Algorithms, 12, 38-56 (1991) · Zbl 0715.68082 |
| [2] | H.-K. Ahn, S.W. Bae, Covering a point set by two disjoint rectangles, in: Proc. 19th Int. Sympos. Alg. Comput. (ISAAC), 2008, pp. 728-739.; H.-K. Ahn, S.W. Bae, Covering a point set by two disjoint rectangles, in: Proc. 19th Int. Sympos. Alg. Comput. (ISAAC), 2008, pp. 728-739. · Zbl 1183.68649 |
| [3] | Atanassov, R.; Bose, P.; Couture, M.; Maheshwari, A.; Morin, P.; Paquette, M.; Smid, M.; Wuhrer, S., Algorithms for optimal outlier removal, J. Discrete Algorithms, 7, 239-248 (2009) · Zbl 1184.68555 |
| [4] | Bespamyatnikh, S.; Segal, M., Covering a set of points by two axis-parallel boxes, Inform. Process. Lett., 95-100 (2000) · Zbl 1338.68255 |
| [5] | Chan, T. M., Geometric applications of a randomized optimization technique, Discrete Comput. Geom., 22, 4, 547-567 (1999) · Zbl 0939.68137 |
| [6] | Chan, T. M., Low-dimensional linear programming with violations, SIAM J. Comput., 34, 4, 879-893 (2005) · Zbl 1075.68092 |
| [7] | Chazelle, B., An algorithm for segment-dragging and its implementation, Algorithmica, 3, 205-221 (1988) |
| [8] | Chazelle, B.; Matoušek, J., On linear-time deterministic algorithms for optimization problems in fixed dimension, J. Algorithms, 21, 3, 579-597 (1996) · Zbl 0864.68040 |
| [9] | Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.; Stein, C., Introduction to Algorithms (2001), MIT Press: MIT Press Cambridge, MA · Zbl 1047.68161 |
| [10] | Das, S.; Goswamib, P. P.; Nandy, S. C., Smallest \(k\)-point enclosing rectangle and square of arbitrary orientation, Inform. Process. Lett., 94, 6, 259-266 (2005) · Zbl 1182.68331 |
| [11] | Dyer, M.; Megiddo, N.; Welzl, E., Linear programming, (Goodman, J. E.; O’Rourke, J., Handbook of Discrete and Computational Geometry (2004), CRC Press), 999-1014 |
| [12] | Fowler, R. J.; Paterson, M. S.; Tanimoto, S. L., Optimal packing and covering in the plane are NP-complete, Inform. Process. Lett., 12, 3, 133-137 (1981) · Zbl 0469.68053 |
| [13] | J.W. Jaromczyk, M. Kowaluk, Orientation independent covering of point sets in \(R^2\); J.W. Jaromczyk, M. Kowaluk, Orientation independent covering of point sets in \(R^2\) |
| [14] | Katz, M. J.; Kedem, K.; Segal, M., Discrete rectilinear 2-center problems, Comput. Geom. Theory Appl., 15, 203-214 (2000) · Zbl 0952.68146 |
| [15] | Lichtenstein, D., Planar formulae and their uses, SIAM J. Comput., 11, 2, 329-343 (1982) · Zbl 0478.68043 |
| [16] | Matoušek, J., On geometric optimization with few violated constraints, Discrete Comput. Geom., 14, 365-384 (1995) · Zbl 0844.90071 |
| [17] | J. Matoušek, P. Škovroň, Three views of LP-type optimization problems, manuscript, 2003.; J. Matoušek, P. Škovroň, Three views of LP-type optimization problems, manuscript, 2003. |
| [18] | Megiddo, N.; Supowit, K. J., On the complexity of some common geometric location problems, SIAM J. Comput., 13, 1, 182-196 (1984) · Zbl 0534.68032 |
| [19] | Saha, C.; Das, S., Covering a set of points in a plane using two parallel rectangles, Inform. Process. Lett., 109, 907-912 (2009) · Zbl 1205.68470 |
| [20] | Segal, M., Lower bounds for covering problems, J. Math. Model. Algorithms, 1, 17-29 (2002) · Zbl 1021.90045 |
| [21] | Segal, M.; Kedem, K., Enclosing \(k\) points in the smallest axis parallel rectangle, Inform. Process. Lett., 65, 95-99 (1998) · Zbl 1338.68269 |
| [22] | Sharir, M.; Welzl, E., A combinatorial bound for linear programming and related problems, (Proc. 9th Sympos. Theoret. Aspects Comput. Sci.. Proc. 9th Sympos. Theoret. Aspects Comput. Sci., LNCS, vol. 577 (1992), Springer-Verlag), 569-579 · Zbl 1494.68276 |
| [23] | M. Sharir, E. Welzl, Rectilinear and polygonal \(pp\); M. Sharir, E. Welzl, Rectilinear and polygonal \(pp\) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
