Research ArticleOpen AccessGoogle Scholar indexed
Variations of Enclosing Problem Using Axis Parallel Square(s): A General Approach
Department of Computer Science and Engineering, University of Kalyani, Kalyani, India
- 1 Department of Computer Science and Engineering, University of Kalyani, Kalyani, India
American Journal of Computational Mathematics·Volume 04 (2014)·Pages 197–205·Published 17 April 2014·DOI10.4236/ajcm.2014.43016
Copy link · social · email
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 , .
KeywordsAxis-Parallel Unit SquareSweep Line AlgorithmMaximium Enclosing ProblemK-Enclosing Problem
- Preparata, F.P. and Shamos, M.I. (1988) Computational Geometry: An Introduction. Springer-Verlag, Berlin.
- 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
- Toussaint, G.T. (1983) Solving Geometric Problems with the Rotating Calipers. Proceedings of IEEE MELECON, Athens, May 1983, 1-8.
- 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
- 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
- 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
- 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
- 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
- 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
- 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.
- 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
- Chazelle, B.M. and Lee, D.T. (1986) On a Circle Placement Problem. Computing, 36, 1-16. http://dx.doi.org/10.1007/BF02238188
- 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.