An O(n2) Algorithm to Compute a Square that contains at least k points

Abstract

Given a set P of n points in two dimensional plane. In this paper we study the minimum enclosing square problem. An O(n2) time
and space algorithm is proposed to locate a minimum enclosing axis-parallel square (Sk) that encloses at least k (1£ k £ n ) points of P .

Keywords: Enclosing problem, Computational Geometry, Facility Location, Covering Location Problem, Algorithm, Optimization Technique.