Home Bookmarks Papers Blog

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

Sariel Har-Peled

Based partially on program written by Gill Barequet

This is the implementation of the algorithm described here.
The code provided below can do the following things:
  1. 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.
  2. 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.
  3. 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].

Source code

Clifford Yapp (brlcad) had kindly repackaged, fixed and updated the code (thanks!). It is now copyrighted under the GPL 2, LGPL 2.1, or MIT license.
  1. Source code:
    libgdiam-1.0.2.tar.gz (08/19/16).
    Old version: libgdiam-1.0.1.tar.gz (08/11/2013).
  2. Building instructions on Linux:

            ~/$ tar -xzf libgdiam-ver.tar.gz
            ~/$ cd libgdiam/
            ~/libgdiam$ mkdir build
            ~/libgdiam$ cd build/
            ~/libgdiam/build$ cmake ..
            ~/libgdiam/build$ make test

Old version

  1. diam_01_26_04_valis.zip.
  2. diam_03_28_01_valis.zip.
  3. diam_10_02_00_valis.zip.

Last modified: Fri Feb 14 09:13:40 CST 2014