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

Priya Ranjan Sinha Mahapatra

Department of Computer Science and Engineering, University of Kalyani, Kalyani, India.

DOI: 10.4236/ajcm.2014.43016                

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 , .

Keywords

Axis-Parallel Unit Square, Sweep Line Algorithm, Maximium Enclosing Problem, K-Enclosing Problem

Conflicts of Interest

The authors declare no conflicts of interest.

References

[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