StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>I have a Perl module that does exactly what you want <a href="http://search.cpan.org/~salva/Algorithm-ClusterPoints-0.08/lib/Algorithm/ClusterPoints.pm" rel="nofollow">Algorithm::ClusterPoints</a>.</p> <p>First, it uses the algorithm you have described in your post to divide the points in multidimensional sectors and then it uses brute force to find clusters between points in adjacent sectors.</p> <p>The complexity varies from O(N) to O(N**2) in very degraded cases. </p> <p><strong>update</strong>:</p> <p>@Denis: no, it is much worse:</p> <p>For <code>d</code> dimensions, the sector (or little hypercube) size <code>s</code> is determined so that its diagonal <code>l</code> is the minimum distance <code>c</code> allowed between two points in different clusters.</p> <pre><code>l = c l = sqrt(d * s * s) s = sqrt(c * c / d) = c / sqrt(d) </code></pre> <p>Then you have to consider all the sectors that touch the hypersphere with diameter <code>r = 2c + l</code> centered in the pivot sector.</p> <p>Roughly, we have to consider <code>ceil(r/s)</code> rows of sectors in every directions and that means <code>n = pow(2 * ceil(r/s) + 1, d)</code>.</p> <p>For instance, for <code>d=5</code> and <code>c=1</code> we get <code>l=2.236</code>, <code>s=0.447</code>, <code>r=3.236</code> and <code>n=pow(9, 5)=59049</code></p> <p>Actually we have to check less neighbor sectors as here we are considering those that touch the hypercube of size <code>(2r+1)/s</code> and we only need to check those touching the circumscribed hypersphere.</p> <p>Considering the bijective nature of the "are on the same cluster" relation we can also half the number of sectors that have to be checked.</p> <p>Specifically, Algorithm::ClusterPoints for the case where <code>d=5</code> checks 3903 sectors.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload