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

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.