An efficient algorithm for the three-dimensional diameter problem

We explore a new approach for computing the diameter of n points in Bbb R ³ that is based on the restriction of the furthest-point Voronoi diagram to the convex hull. We show that the restricted Voronoi diagram has linear complexity. We present a deterministic algorithm with O(nlog ² n) running time. The algorithm is quite simple and is a good candidate to be implemented in practice. Using our approach the chromatic diameter and all-furthest neighbors in Bbb R ³ can be found in the same running time. Received February 18, 2000, and in revised form June 27, 2000. Online publication January 17, 2001.