4
$\begingroup$

Given a vector of points (on the 2D plane), what is the fastest algorithm to find all pairs of points at a distance of 1?

Of course, I could use the $O(N^2)$ algorithm to check all pairs of points. However, I recently found out that there are at most $O(N^{4/3})$ points which satisfy the property, so I am wondering if a quicker algorithm exists.

Thanks!

$\endgroup$

2 Answers 2

1
$\begingroup$

You may use a Well-Separated Pairs Decomposition (WSPD). This is a hierarchical decomposition, where at each level, you split the points into two parts, each of them a certain distance from the sphere enclosing the other set, and a certain radius of the sphere containing them.

It runs in $O(n\log n + X)$, where $X$ is an output sensitive parameter, that measures the number of the partitions required to make the full decomposition. (Of course, you can stop the decomposition algorithm after you are working with distances less than 1)

$\endgroup$
3
  • $\begingroup$ This reduces the problem to the bipartite case but it is not clear how to enumerate unit distance pairs in a decomposition set pair $(A_i, B_i)$. Could you clarify it? $\endgroup$
    – pcpthm
    Jan 19, 2022 at 5:45
  • $\begingroup$ You run the same procedure recursively. $\endgroup$
    – Discrete lizard
    Jan 19, 2022 at 6:17
  • 1
    $\begingroup$ For example, let the point set be $A \cup B$ where $A = \{ 0 + \epsilon_i \}_{i=1}^{n/2}, B = \{ 1 + \epsilon_i \}_{i=n/2+1}^n$, $0 < \epsilon_i \ll 1 \; \forall i$. The WSPD contains a pair $(A, B)$, but how to enumerate pairs $a \in A, b \in B, |a - b| = 1$ in $o(n^2)$ time? $\endgroup$
    – pcpthm
    Jan 19, 2022 at 6:50
1
$\begingroup$

The problem can be regarded as a special case of incidence reporting problem with $N$ unit circles and $N$ points in the plane.

If the number of unit circles is $m$, then this problem can be solved in $\tilde{O}(m^2 + N)$ time ($\tilde{O}(\cdot)$ ignores polylogarithmic factors). First, explicitly computing the arrangement (the division of the plane, its edges, and vertices) of circles, then constructing a point location data structure, and query the data structure for each point.

The set of $N$ circles can be partitioned into $\sqrt N$ subsets of each $\sqrt N$ size, and each sub-problem can be solved separately. The total runtime is $\tilde{O}(N^{3/2})$. A more involved approach yields a $\tilde{O}(N^{4/3})$-time randomized algorithm [1].

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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