The Algorithm Design Manual
About the Book
Programming Challenges

The Stony Brook Algorithm Repository

Steven Skiena
Stony Brook University
Dept. of Computer Science

Program - A Practical Approach for Computing the Diameter of a Point-Set

Author's notes:

We present a new simple approximation algorithm for computing the diameter of a point-set in d-dimensions. The new algorithm is sensitive to the ``hardness'' of computing the diameter of the given input, and for most inputs it is able to compute the exact diameter extremely fast. The algorithm can be implemented quickly, and it is robust. As such, this algorithm seems to be the algorithm of choice in practice for computing/approximating the diameter.

  • Download Files (local site)
  • Offical Site

    Problem Links

    Bin Packing (7)

    This page last modified on 2008-07-10 .