Smallest k-point enclosing rectangle and square of arbitrary orientation |
| |
Authors: | Sandip Das Partha P Goswami |
| |
Affiliation: | a Indian Statistical Institute, Kolkata 700 108, India b Calcutta University, Kolkata 700 029, India |
| |
Abstract: | 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+kn2(n−k)logn) time. |
| |
Keywords: | Levels of arrangement Plane sweep Computational geometry Optimization |
本文献已被 ScienceDirect 等数据库收录! |
|