Smallest axis-parallel rectangle enclosing at least k points
Priya Ranjan, Priya Ranjan Sinha Mahapatra · 2012
Let P be a set of n points on a two-dimensional plane. In this work, we present an algorithm that identies a smallest area axis-parallel rectangle enclosing at least k points of P (1 < k n). The worst case time and space complexities of the algorithm are O(n 4 ) and O(n 2 ) respectively.