Variations of Enclosing Problem Using Axis Parallel Square(s): A General Approach

Abstract

Let P be a set of n points in two dimensional plane. For each point , we locate an axis- parallel unit square having one particular side passing through p and enclosing the maximum number of points from P. Considering all points , such n squares can be reported in O(nlogn) time. We show that this result can be used to (i) locate m>(2) axis-parallel unit squares which are pairwise disjoint and they together enclose the maximum number of points from P (if exists) and (ii) find the smallest axis-parallel square enclosing at least k points of P , .

Share and Cite:

Mahapatra, P. (2014) Variations of Enclosing Problem Using Axis Parallel Square(s): A General Approach. American Journal of Computational Mathematics, 4, 197-205. doi: 10.4236/ajcm.2014.43016.

Conflicts of Interest

The authors declare no conflicts of interest.

 [1] Preparata, F.P. and Shamos, M.I. (1988) Computational Geometry: An Introduction. Springer-Verlag, Berlin. [2] Chandran, S. and Mount, D. (1992) A Parallel Algorithm for Enclosed and Enclosing Triangles. International Journal of Computational Geometry and Applications, 2, 191-214. http://dx.doi.org/10.1142/S0218195992000123 [3] Toussaint, G.T. (1983) Solving Geometric Problems with the Rotating Calipers. Proceedings of IEEE MELECON, Athens, May 1983, 1-8. [4] O’Rourke, J. (1985) Finding Minimal Enclosing Boxes. International Journal of Computer and Information Sciences, 14, 183-199. http://dx.doi.org/10.1007/BF00991005 [5] Agarwal, P.K., Sharir, M. and Toledo, S. (1994) Applications of Parametric Searching in Geometric Optimization. Journal of Algorithms, 17, 292-318. http://dx.doi.org/10.1006/jagm.1994.1038 [6] Aggarwal, A., Imai, H., Katoh, N. and Suri, S. (1991) Finding k Points with Minimum Diameter and Related Problems, Journal of Algorithms, 12, 38-56. http://dx.doi.org/10.1016/0196-6774(91)90022-Q [7] Eppstein, D. and Erickson, J. (1994) Iterated Nearest Neighbors and Finding Minimal Polytopes. Discrete and Computational Geometry, 11, 321-350. http://dx.doi.org/10.1007/BF02574012 [8] Datta, A., Lenhof, H.P., Schwarz, C. and Smid, M. (1995) Static and Dynamic Algorithms for k-Point Clustering Problems. Journal of Algorithms, 19, 474-503. http://dx.doi.org/10.1006/jagm.1995.1048 [9] Segal, M. and Kedem, K. (1998) Enclosing k Points in Smallest Axis Parallel Rectangle. Information Processing Letters, 65, 95-99. http://dx.doi.org/10.1016/S0020-0190(97)00212-3 [10] Das, S., Goswami, P.P. and Nandy, S.C. (2005) Smallest k-Point Enclosing Rectangle and Square of Arbitrary Orientation. Information Processing Letters, 95, 259-266. [11] Ahn, H., Won, B.S., Demaine, E.D., Demaine, M.L., Kim, S., Korman, M., Reinbacher, I. and Son, W. (2011) Covering Points by Disjoint Boxes with Outliers. Computational Geometry: Theory and Applications, 44, 178-190. http://dx.doi.org/10.1016/j.comgeo.2010.10.002 [12] Chazelle, B.M. and Lee, D.T. (1986) On a Circle Placement Problem. Computing, 36, 1-16. http://dx.doi.org/10.1007/BF02238188 [13] Barequet, G., Dickerson, M. and Pau, P. (1997) Translating a Convex Polygon to Contain a Maximum Number of Points. Computational Geometry: Theory and Applicaions, 8, 167-179. [14] Barequet, G., Briggs, A.J., Dickerson, M.T. and Goodrich, M.T. (1998) Offset-Polygon Annulus Placement Problems. Computational Geometry: Theory and Applications, 11, 125-141. [15] Younies, H. and Wesolowsky, G.O. (2004) A Mixed Integer Formulation for Maximal Covering by Inclined Paralleograms. European Journal of Operational Research, 159, 83-94. http://dx.doi.org/10.1016/S0377-2217(03)00389-8 [16] Daz-Bánez, J.M., Seara, C., Antoni, S.J., Urrutia, J. and Ventura, I. (2005) Covering Points Sets with Two Convex Objects. Proceedings of 21st European Workshop on Computational Geometry, 179-182. [17] Cabello, S., Miguel, D.B.J., Seara, C., Sellares, J.A., Urrutia, J. and Ventura, I. (2008) Covering Point Sets with Two Disjoint Disks or Squares. Computational Geometry: Theory and Applicaions, 40, 195-206. http://dx.doi.org/10.1016/j.comgeo.2007.10.001 [18] De Berg, M., Van Kreveld, M., Overmars, M. and Schwarzkopf, O. (2000) Computational Geometry—Algorithms and Applications, Springer-Verlag, Berlin. [19] Megiddo, N. and Supowit, K.J. (1984) On the Complexity of Some Common Geometric Location Problems. SIAM Journal of Computing, 13, 182-196. http://dx.doi.org/10.1137/0213014 [20] Lengauer, T. (1988) Combinatorial Algorithms for Integrated Circuit Layout, Berlin. [21] Mukherjee, M. and Chakraborty, K. (2002) A Polynomial-Time Optimization Algorithm for a Rectlinear Partitioning Problem with Applications in VLSI Design Automation. Information Processing Letters, 83, 41-48. http://dx.doi.org/10.1016/S0020-0190(01)00305-2 [22] Matousek, J. (1995) On Geometric Optimization with Few Violated Constraints. Discrete and Computational Geometry, 14, 365-384. http://dx.doi.org/10.1007/BF02570713