Find two most distant points in a set of points in 3D space
<p>I need to find the diameter of the points cloud (two points with maximum distance between them) in 3-dimensional space. As a temporary solution, right now I'm just iterating through all possible pairs and comparing the distance between them, which is a very slow, <code>O(n^2)</code> solution.</p>

<p>I believe it can be done in <code>O(n log n)</code>. It's a fairly easy task in 2D (just find the <strong>convex hull</strong> and then apply the <strong>rotating calipers</strong> algorithm), but in 3D I can't imagine how to use rotating calipers, since there is no way to order the points. </p>

<p>Is there any simple way to do it (or ready-to-use implementation in <code>python</code> or <code>C/C++</code>)? </p>

<p><strong>PS</strong>: There are similar questions on StackOverflow, but the answers that I found only refers to Rotating Calipers (or similar) algorithms, which works fine in 2D situation but not really clear how to implement in 3D (or higher dimensionals). </p>

<p>While O(n log n) expected time algorithms exist in 3d, they seem tricky to implement (while staying competitive to brute-force O(n^2) algorithms).</p>

<p>An algorithm is described in <a href="http://dl.acm.org/citation.cfm?id=378662" rel="nofollow">Har-Peled 2001</a>. The authors provide a <a href="http://sarielhp.org/research/papers/00/diam.html" rel="nofollow">source code</a> than can optionally be used for optimal computation. I was not able to download the latest version, the "old" version could be enough for your purpose, or you might want to contact the authors for the code.</p>

<p>An alternative approach is presented in <a href="http://www.worldscientific.com/doi/abs/10.1142/S0218195902001006" rel="nofollow">Malandain &amp; Boissonnat 2002</a> and the authors <a href="http://www-sop.inria.fr/members/Gregoire.Malandain/diameter/" rel="nofollow">provide code</a>. Altough this algorithm is presented as approximate in higher dimensions, it could fit your purpose. Note that their code provide an implementation of Har-Peled's method for exact computation that you might also check.</p>

<p>In any case, in a real-world usage you should always check that your algorithm remains competitive with respect to the naÃ¯ve O(n^2) approach.</p>

python c++ geometry convex-hull