Enclosing k points in the smallest axis parallel rectangle
Michael Segal, Klara Kedem · Canadian Conference on Computational Geometry · 1996
We consider the following clustering problem. Given a set S of n points in the plane, and given an integer k, n 2 ! k n, we want to find the smallest axis parallel rectangle (smallest perimeter or area) that encloses exactly k points of S. We present an algorithm which runs in time O(n + k(n \\Gamma k) 2 ) improving previous algorithms which run in time O(k 2 n) and do not perform well for larger k values. We present an algorithm to enclose k of n given points in an axis parallel box in d-dimensional space which runs in time O(dn+dk(n \\Gamma k) 2(d\\Gamma1) ) and occupies O(dn) space. We slightly improve algorithms for other problems whose runtimes depend on k.