Efficient ways to sort pairwise distances for set of points in Euclidean space?

Question

Consider a Euclidean space $\mathbb{R}^d$. Consider $ X \subset \mathbb{R}^d$ where $X$ is a finite set with $|X|=n$. Consider the set of line segments $\{xy | x,y \in X\}$ . I have a process $Z$ that I want to apply to each line segment, from smallest to largest but I will stop examining line segments when a line segment satisfies some condition $C$.

One thing I could do is find all line segments and then order them from smallest to largest and simply apply $Z$ to each line segment until $C$ is satisfied but organising the line segments will have $O(n^2\log (n))$ complexity.

Is there an efficient way I can find each line segment in order of increasing length, one at a time.

That is, find a line segment $l$, apply $Z$ to $l$ and if $C$ is not satisfied find the next largest line segment, apply $Z$,...

Thank you in advance

• D.W.: If this is a practical problem, can you give us an idea how large $d$ will typically be? The appropriate algorithms for $d=2$ are very different from those when $d$ is large. (See also en.wikipedia.org/wiki/Closest_pair_of_points_problem, en.wikipedia.org/wiki/Nearest_neighbor_search.)

Answer 1

A better solution could be as follows:

1. Create a min heap over $n^2$ line segments.
2. Take the top element of the heap, check if it satisfies condition $C$. If it does not satisfy it, pop it out. If it satisfies the condition, stop.

Step 1ドル$, take $O(n^2)$ time. Step 2ドル$ takes $O(p \log n)$ time, where $p$ is the position of the first line segment in the sorted order that satisfies the condition $C$.

If $p$ is small, the algorithm takes $O(n^2)$ time.