Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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!
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)
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].
