Enclosing k points in the smallest axis parallel rectangle Academic Article uri icon

abstract

  • We consider the following clustering problem. Given a set S of n points in the plane, and given an integer k , n 2 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 − 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 − k ) 2( d − 1) and occupies O ( dn ) space. We slightly improve algorithms for other problems whose runtimes depend on k .

publication date

  • January 1, 1998