Smallest k-point enclosing rectangle and square of arbitrary orientation

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(n2logn+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(n2logn+kn(n−k)2logn) time.