Program A Practical Approach for Computing the Diameter of a
Point-Set
Sariel Har-Peled
Based on program written by Gill Barequet
This is the implementation of the algorithm described
here.
The code provided below can do the following things:
Compute the exact diameter of a point-set in 3d. Seems to be
linear time for most ``real'' inputs. Can be quadratic in the worst case.
Approximate the diameter of a point-set up to a prespecified
approximation parameter. Running-time depends on the parameter, and
for reasonable value of this parameter it is linear.
Compute a tight-fitting bonding-box that contains a given input
point-set. The bounding box is arbitrarly oriented. Based on the paper
and code of [Barequet and
Har-Peled, 99].
Code for computing/approximating the diameter: gdiam.C, gdiam.h.