Abstract
Let P be a set of n points in the plane. Here we present an efficient algorithm to compute the smallest square containing at least k points of P for large values of k. The worst case time complexity of the algorithm is O(n + (n − k)log2 (n − k)) using O(n) space which is the best known bound for worst case time complexity.
A preliminary version of this paper was presented at an informal event SPSITM 2011.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Aggarwal, A., Imai, H., Katoh, N., Suri, S.: Finding k points with minimum diameter and related problems. Journal of Algorithms 12, 38–56 (1991)
Agarwal, P.K., Sharir, M., Toledo, S.: Applications of parametric searching in geometric optimization. Journal of Algorithms 17, 292–318 (1994)
Ahn, H.-K., Won, B.S., Demaine, E.D., Demaine, M.L., Kim, S.-S., Korman, M., Reinbacher, I., Son, W.: Covering points by disjoint boxes with outliers. Computational Geometry: Theory and Applications 44, 178–190 (2011)
Andrews, H.C.: Introduction to mathematical techniques in pattern recognition. Wiley-Intersciences, New York (1972)
Asano, T., Bhattacharya, B., Keil, M., Yao, F.: Clustering algorithms based on maximum and minimum spanning trees. In: Proc. 4th Annual Symposium on Computational Geometry, pp. 252–257 (1988)
de Berg, M., Van Kreveld, M., Overmars, M., Schwarzkopf, O.: Computational Geometry: Algorithms and Applications. Springer, Berlin (1997)
Chan, T.M.: Geometric Applications of a Randomized Optimization Technique. Discrete Computational Geometry 22, 547–567 (1999)
Das, S., Goswami, P.P., Nandy, S.C.: Smallest k-point enclosing rectangle and square of arbitrary orientation. Information Processing Letters 94, 259–266 (2005)
Drezner, Z., Hamacher, H.: Facility Location: Applications and Theory. Springer, Berlin (2002)
Datta, A., Lenhof, H.E., Schwarz, C., Smid, M.: Static and dynamic algorithms for k-point clustering problems. In: Dehne, F., Sack, J.-R., Santoro, N. (eds.) WADS 1993. LNCS, vol. 709, pp. 265–276. Springer, Heidelberg (1993)
Datta, A., Lenhof, H.E., Schwarz, C., Smid, M.: Static and Dynamic Algorithms for k-point Clustering Problems. Journal of Algorithms 19, 474–503 (1995)
Eppstein, D., Erickson, J.: Iterated nearest neighbors and finding minimal polytopes. Discrete Computational Geometry 11, 321–350 (1994)
Hartigan, J.A.: Clustering Algorithms. Wiley, New York (1975)
Megiddo, N.: Linear-Time Algorithms for Linear Programming in ℝ3 and Related Problems. SIAM Journal Computing 12, 759–776 (1995)
Matoušek, J.: On geometric optimization with few violated constraints. Discrete Computational Geometry 14, 365–384 (1995)
Majumder, S., Bhattacharya, B.B.: Density or Discrepancy: A VLSI Designer’s Dilemma in Hot Spot Analysis. Information Processing Letter 107, 177–182 (2008)
Mehlhorn, K.: Data structures and algorithms 3: multi-dimensional searching and computational geometry. Springer, New York (1984)
O’Rourke, J., Aggarwal, A., Maddila, S., Baldwin, M.: An optimal algorithm for finding minimal enclosing triangles. Journal of Algorithms 7, 258–269 (1986)
O’Rourke, J.: Finding minimal enclosing boxes. International Journal of Computer and Information Sciences 14, 183–199 (1985)
Preparata, F.P., Shamos, M.I.: Computational Geometry: an Introduction. Springer, Berlin (1990)
Segal, M., Kedem, K.: Enclosing k points in the smallest axis parallel rectangle. Information Processing Letter 65, 95–99 (1998)
Smid, M.: Finding k Points with a Smallest Enclosing Square, Report MPI-92-152, Max-Plank-Institute fur Informatik, Saarbriucken (1992)
Toussaint, G.T.: Solving geometric problems with the rotating calipers. In: Proc. IEEE MELECON (1983)
Welzl, E.: Smallest enclosing disks (balls and ellipses). In: Maurer, H.A. (ed.) New Results and New Trends in Computer Science. LNCS, vol. 555, pp. 359–370. Springer, Heidelberg (1991)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Mahapatra, P.R.S., Karmakar, A., Das, S., Goswami, P.P. (2011). k-Enclosing Axis-Parallel Square. In: Murgante, B., Gervasi, O., Iglesias, A., Taniar, D., Apduhan, B.O. (eds) Computational Science and Its Applications - ICCSA 2011. ICCSA 2011. Lecture Notes in Computer Science, vol 6784. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-21931-3_7
Download citation
DOI: https://doi.org/10.1007/978-3-642-21931-3_7
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-21930-6
Online ISBN: 978-3-642-21931-3
eBook Packages: Computer ScienceComputer Science (R0)