ENCLOSING K-POINTS IN THE SMALLEST AXIS PARALLEL RECTANGLE

We consider the following clustering problem. Given a set S of n point s in the plane, and given an integer k, n/2 < k less than or equal to n, we want to find the smallest axis parallel rectangle (smallest peri meter or area) that encloses exactly k points of S. We present an algo rithm which runs in time O(n + k(n - k)(2)) improving previous algorit hms which run in time O(k(2)n) and do not perform well for larger k va lues. We present an algorithm to enclose k of n given points in an axi s parallel box in d-dimensional space which runs in time O(dn + dk(n - k)(2(d-1))) and occupies O(dn) space. We slightly improve algorithms for other problems whose runtimes depend on k. (C) 1998 Elsevier Scien ce B.V.