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

DOI: 10.4236/ajcm.2014.43016   PDF   HTML     4,905 Downloads   6,044 Views  


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.
[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.
[5] Agarwal, P.K., Sharir, M. and Toledo, S. (1994) Applications of Parametric Searching in Geometric Optimization. Journal of Algorithms, 17, 292-318.
[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.
[7] Eppstein, D. and Erickson, J. (1994) Iterated Nearest Neighbors and Finding Minimal Polytopes. Discrete and Computational Geometry, 11, 321-350.
[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.
[9] Segal, M. and Kedem, K. (1998) Enclosing k Points in Smallest Axis Parallel Rectangle. Information Processing Letters, 65, 95-99.
[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.
[12] Chazelle, B.M. and Lee, D.T. (1986) On a Circle Placement Problem. Computing, 36, 1-16.
[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.
[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.
[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.
[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.
[22] Matousek, J. (1995) On Geometric Optimization with Few Violated Constraints. Discrete and Computational Geometry, 14, 365-384.

comments powered by Disqus

Copyright © 2020 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.