查看文章

Given a set of n points in 2D, the problem of identifying the smallest rectangle of arbitrary orientation, and containing exactly k(⩽n) points is studied in this paper. The worst case time and space complexities of the proposed algorithm are O(n²logn+nk(n−k)(n−k+logk)) and O(n), respectively. The algorithm is then used to identify the smallest square of arbitrary orientation, and containing exactly k points in O(n²logn+kn(n−k)²logn) time.