Enclosing k points in the smallest axis parallel rectangle

✍ Scribed by Michael Segal; Klara Kedem

• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 445 KB
• Volume: 65
• Category: Article
• ISSN: 0020-0190
• DOI: 10.1016/s0020-0190(97)00212-3

✦ Synopsis

We consider the following clustering problem. Given a set S of II 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 0( n + k( n -k)*) improving previous algorithms which run in time 0(&r) 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(h) space. We slightly improve algorithms for other problems whose mntimes depend on k. @ 1998 Elsevier Science B.V.