Finding k points with a smallest enclosing square
Michiel Smid · MPG.PuRe (Max Planck Society) · 1993
An algorithm is presented that, given a set of $n$ points in the plane and an integer $k$, $2 \\leq k \\leq n$, finds $k$ points with a smallest enclosing axes-parallel square. The algorithm has a running time of $O(n \\log n + kn \\log^{2} k)$ and uses $O(n)$ space. The previously best known algorithm for this problem takes $O(k^{2} n \\log n)$ time and uses $O(kn)$ space.