Back
 AJCM  Vol.4 No.3 , June 2014
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 , .
Cite this paper: 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.
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

 
 
Top