ON THE COMPUTATION OF MINIMUM ENCASING RECTANGLES AND SET DIAMETERS
Donald C. S. Allison, M. T. Noga · Computer Science Technical Reports (Virginia Tech) · 1981
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.