Abstract
We investigate two kinds of optimization problems regarding points in the 2-dimensional plane that need to be enclosed by squares.
-
(1)
Given a set of \(n\) points, find a given number of squares that enclose all the points, minimizing the size of the largest square used.
-
(2)
Given a set of \(n\) points, enclose the maximum number of points, using a specified number of squares of a fixed size. We provide different techniques to solve the above problems in cases where squares are axis-parallel or of arbitrary orientation, disjoint or overlapping. All the algorithms we use run in time that is a low-order polynomial in \(n\).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
This polygon may be the convex hull of the points in \(\mathcal P\) computed in \(O(n \log n)\) time.
- 2.
Since the points in \(\mathcal{P}'_l {\setminus }\{a, b, c, d\}\) cannot affect the size of the left square, they can be pruned.
- 3.
To be exact, \(\mathcal{P}_1\) (resp. \(\mathcal{P}_2\), \(\mathcal{P}_3\)) covers the first \(\lceil n/3\rceil \) (resp. next \(\lfloor n/3\rfloor \), the remaining \(\lceil n/3\rceil \) or \(\lfloor n/3\rfloor \)) points. They can be determined in linear time [2]. So the difference is at most one.
References
Agarwal, P.K., Sharir, M.: Planar geometric locations problems. Algorithmica 11, 185–195 (1994)
Blum, M., Floyd, R., Pratt, V., Rivest, R., Tarjan, R.: Time bounds for selection. J. Comput. Syst. Sci. 7(4), 448–461 (1973)
Cabello, S., DÃaz-Báñez, J.M., Seara, C., Sellares, J.A., Urrutia, J., Ventura, I.: Covering point sets with two disjoint disks or squares. Comput. Geom. 40(3), 195–206 (2008)
Chandran, S., Mount, D.: A parallel algorithm for enclosed and enclosing triangles. Int. J. Comput. Geom. Appl. 2, 191–214 (1992)
Christofides, N., Hadjiconstantinou, E.: An exact algorithm for orthogonal 2-D cutting problems using guillotine cuts. Eur. J. Oper. Res. 83(1), 21–38 (1995)
Das, S., Goswami, P.P., Nandy, S.C.: Smallest \(k\)-point enclosing rectangle and square of arbitrary orientation. Inform. Process. Letts. 94, 259–266 (2005)
Hoffmann, C.M.: Robustness in geometric computations. J. Comput. Inf. Sci Eng. 1(2), 143–155 (2001)
Jaromczyk, J.W., Kowaluk, M.: Orientation independent covering of point sets \(R^{2}\) with pairs of rectangles or optimal squares. In: Proceedings of the European Workshop on Computational Geometry. LNCS, vol. 871, pp. 71–78. Springer, Heidelberg (1996)
Katz, M.J., Kedem, K., Segal, M.: Discrete rectilinear 2-center problems. Comput. Geom. 15(4), 203–214 (2000)
Kim, S.S., Bae, S.W., Ahn, H.K.: Covering a point set by two disjoint rectangles. Int. J. Comput. Geom. Appl. 21(3), 313–330 (2011)
Klee, V., Laskowski, M.: Finding the smallest triangles containing a given convex polygon. J. Algorithms 6, 359–375 (1985)
Mahapatra, P.R.S., Goswami, P.P., Das, S.: Covering points by isothetic unit squares. In: Proceedings of the Canadian Conference on Computational Geometry (CCCG), pp. 169–172 (2007)
Mahapatra, P.R.S., Goswami, P.P., Das, S.: Maximal covering by two isothetic unit squares. In: Proceedings of the Canadian Conference on Computational Geometry (CCCG), pp. 103–106 (2008)
Melkman, A.A.: On-line construction of the convex hull of a simple polyline. Inform. Process. Letts. 25(1), 11–12 (1987)
O’Rourke, J.: Finding minimal enclosing boxes. Int. J. Comput. Inf. Sci. 14, 183–199 (1985)
O’Rourke, J., Aggarwal, A., Maddila, S., Baldwin, M.: An optimal algorithm for finding minimal enclosing triangles. J. Algorithms 7, 258–269 (1986)
Preparata, F., Shamos, M.: Computational Geometry: An Introduction. Springer, Berlin (1990)
Segal, M.: Lower bounds for covering problems. J. Math. Model. Algorithms 1, 17–29 (2002)
Sharir, M., Welzl, E.: Rectilinear and polygonal \(p\)-piercing and \(p\)-center problems. In: ACM Symposium on Computational Geometry, pp. 122–132 (1996)
Toussaint, G.: Solving geometric problems with the rotating calipers. In: Proceedings of the IEEE MELECON (1983)
Welzl, E.: Smallest enclosing disks (balls and ellipses). In: Maurer, H.A. (ed.) New Results and Trends in Computer Science. LNCS, vol. 555, pp. 359–370. Springer, Heidelberg (1991)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Bhattacharya, B., Das, S., Kameda, T., Sinha Mahapatra, P.R., Song, Z. (2014). Optimizing Squares Covering a Set of Points. In: Zhang, Z., Wu, L., Xu, W., Du, DZ. (eds) Combinatorial Optimization and Applications. COCOA 2014. Lecture Notes in Computer Science(), vol 8881. Springer, Cham. https://doi.org/10.1007/978-3-319-12691-3_4
Download citation
DOI: https://doi.org/10.1007/978-3-319-12691-3_4
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-12690-6
Online ISBN: 978-3-319-12691-3
eBook Packages: Computer ScienceComputer Science (R0)