Time-Optimal Algorithm for Computing the Diameter of a Point Set on a Completely Overlapping Network
Prapaporn Techa-Angkoon, S. Rattanaudomsawat · 2009
Abstract- Given a finite set P of n points in d-dimensional Euclidean space, the diameter is defined as the maximum Euclidean distance between any two points in the set P. In this paper, we illustrate a time-optimal algorithm to compute the diameter of a point set on a theoretical network called a completely overlapping network (CON). This network model has an applicable potential in real-life applications because it is an extension of LANs that are widely used at present. Index Terms- computational geometry, diameter, overlapping network, time-optimal algorithm. I.