On the Computation of Minimum Encasing Rectangles and Set Diameters
Files
TR Number
CS81017-R
Date
1981
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Department of Computer Science, Virginia Polytechnic Institute & State University
Abstract
Two new algorithms are described for the following problems: given a set of N points in the plane determine (i) the rectangle of minimum area which will completely cover (or encase) the set and (ii) the two points that are farthest apart (diameter of the set). Both algorithms have O(NlogN) time complexity and are based upon a similar strategy.