An Efficient Algorithm for the Three-Dimensional Diameter Problem

Abstract: We explore a new approach for computing the diameter of n points in 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 R³ can be found in the same running time.

@article{b-eatddp-01,
author = "S. Bespamyatnikh",
title = "An Efficient Algorithm for the Three-Dimensional Diameter Problem",
journal = "Discrete Comput. Geom.",
year = 2001,
volume = 25,
number = 2,
pages = "235--255"
}