Information Processing Letters 45 (1993) 269-274.
A Simple Algorithm for Enumerating Longest Distances in the Plane
Matthew T. Dickerson and Jason Shugart
Abstract
We present a deterministic algorithm that takes as input a set of n points in the plane and enumerates in descending order the k longest distances between pairs of points. The algorithm works for all Lp distance metrics, requires O(n+k) space, and for uniform distributions over natural containing shapes, has expected case running time of O(nlogn+klogklogn/loglogn).