Computing the Diameter of a Point Set

Given a finite set of points P in R^d, the diameter of P is defined as the maximum distance between two points of P. We propose a very simple algorithm to compute the diameter of a finite set of points. Although the algorithm is not worst-case optimal, it appears to be extremely fast for a large variety of point distributions.

Implementation

• The implementation of the algorithm for computing/approximating the diameter is available by anonymous ftp: diameter-0.01.zip or diameter-0.01.tar.gz
  • can be tested with real inputs or random distributions
  • works for points in R^d
  • contains also an implementation of Har-Peled's method (for the exact computation of the diameter) that works in R^d

• Research report

  @TechReport{Malandain:Boissonnat:RR:2001,
  author = {Malandain, Grégoire and Boissonnat, Jean-Daniel},
  title = {Computing the Diameter of a Point Set},
  institution = {INRIA},
  year = {2001},
  type = {Research report},
  number = {RR-4233},
  address = {Sophia-Antipolis},
  month = jul,
  url = "http://www.inria.fr/rrrt/rr-4233.html",
  keyword = {computational geometry} 
  }
  

• Communication at DGCI 2002

  @InProceedings{malandain-boissonnat:dgci:2002,
    author = 	 {Grégoire Malandain and Jean-Daniel Boissonnat},
    title = 	 {Computing the Diameter of a Point Set},
    booktitle = 	 {Discrete Geometry for Computer Imagery (DGCI 2002)},
    OPTpages = 	 {197--208},
    year = 	 {2002},
    editor = 	 {A. Braquelaire and J.-O. Lachaud and A. Vialard},
    volume = 	 {2301},
    series = 	 {LNCS},
    address = 	 {Bordeaux, France},
    publisher = {Springer},
    note = 	 {also INRIA research report RR-4233},
    keyword = {computational geometry}
  }
  

  • Postscript
  • PDF
  • Presentation (slides)
• Article in International Journal of Computational Geometry & Applications

  @ARTICLE{malandain-boissonnat:ijcga:2002,
     AUTHOR       = {Gr\'egoire Malandain and Jean-Daniel Boissonnat},
     JOURNAL      = {International Journal of Computational Geometry \& Applicatio
  ns},
     TITLE        = {Computing the Diameter of a Point Set},
     YEAR         = {2002},
     MONTH        = {December},
     OPTNOTE      = {},
     NUMBER       = {6},
     PAGES        = {489--510},
     VOLUME       = {12}
  

Links

• A Practical Approach for Computing the Diameter of a Point-Set, Sariel Har-Peled

[Home page] [Publications] [Epidaure team] [Epidaure on-going research]