2
$\begingroup$

I haven't been able to find literature on the efficient solving of the following problem.

Given $n$ random points $x_i \in (0, 1)^2$ the unit square, obtain the flat clusters of points, such that two points are in the same cluster if their pairwise distance $d(x_i, x_j) < r$, where $r < 1$ is a fixed parameter of the problem.

The naive solution checks each pairwise distance, therefore completing in $\mathcal{O}(n^2)$ time. Is there a faster way, assuming $n$ large and $r \ll 1$?

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ Build a r-tree in O($n\log n$), use it to improve the lookup time. $\endgroup$ – adrianN Oct 28 '16 at 13:28
  • $\begingroup$ You can superimpose an $r$-by-$r$ grid on the unit square and map each point to its grid cell. Then you only need to need to check other points in the same cell and its 8 neighbours. (This doesn't eliminate the $n^2$ factor, but should give a large speedup in practice for small $r$.) $\endgroup$ – j_random_hacker Oct 28 '16 at 13:28
  • $\begingroup$ @j_random_hacker, that's actually what I'm using now, but I was wondering if I was overlooking any huge speedups. I'm not familiar with r-tree, but what would the cost of the total algorithm be? $\endgroup$ – Kappie001 Oct 28 '16 at 13:45
  • $\begingroup$ I'm struggling to understand what you want the output to be. Suppose you have points $(0,0)$, $(0.5,0)$, and $(1,0)$, and $r=0.6$. Do you want the output to be a single cluster containing all three points? Or something else? The relation "$d(x_ix_j)<r$" is not transitive, so I'm not sure how the cluster should be defined. $\endgroup$ – D.W.♦ Oct 30 '16 at 2:20
  • $\begingroup$ @D.W. They would all be in the same cluster. See percolation theory on wikipedia. The main question, in the end, is at which $r$ a giant cluster (that scales with $n$) forms. $\endgroup$ – Kappie001 Oct 30 '16 at 9:11
2
$\begingroup$

The following algorithm does unfortunately does not allow you to get the $n^2$ factor out (see comment below).

Superimpose an $r/\sqrt 2$-by-$r/\sqrt 2$ grid on the unit square: notice that every point within the same grid cell is automatically within the same cluster. Also notice that there can be at most $n$ grid cells containing one or more points; these are the only grid cells we need to consider from this point on.

  1. Map each point to its grid cell.
  2. For each grid cell, throw all contained points into the same cluster.
  3. For each pair of neighbouring grid cells $P$, $Q$ (each grid cell, apart from those at edges and corners, has 8 such neighbours), determine the closest pair of points $p, q$ having $p \in P$ and $q \in Q$ using this $O(n\log n)$ algorithm. If $d(p, q) < r$ then combine $C(P)$ and $C(Q)$, otherwise not.

You can use a union/find disjoint set data structure to maintain the clusters in close-to-linear time, just as per the Kruskal algorithm.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ I've just realised that, despite my (italicised!) claim, my answer doesn't get the $n^2$ factor out of the time complexity, because that can only happen if we know that every pair of points within each grid cell are separated by at least some minimum distance -- a condition that holds in the original closest-pair problem, but not here. It might be possible to salvage something with the Triangle Inequality, but after thinking about it for a while I don't have anything. Let me know if I should delete this. $\endgroup$ – j_random_hacker Nov 4 '16 at 17:10
  • 1
    $\begingroup$ So the core issue is whether it's possible to do the following in $O(n \log n)$ time? Given sets $P,Q$ of points, find the closest pair of points $p,q$ such that $p \in P$ and $q \in Q$. That seems worth posting as a separate question in its own right... when I get a chance I may do that. $\endgroup$ – D.W.♦ Nov 4 '16 at 18:33
  • 1
    $\begingroup$ Asked here: cs.stackexchange.com/q/65573/755 $\endgroup$ – D.W.♦ Nov 5 '16 at 3:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.