On the Computation of Minimum Encasing Rectangles and Set Diameters

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.