Connect any two points in 2 dimensional space

Question

Is there any algorithm better than O(n^2) to connect any two points by a straight line as long as their distance is lesser than a constant t?

I am thinking about sort the points according to their x-coordinate, then looking for another point within [x-t, x+t]. But the worst case is still O(n^2). Any idea? Do we have any special data structure to speed up?

Answer 1

One approach that may help is to compute a bucket for each point as:

int(x/t),int(y/t)

i.e. points (0.1,0.9), (0.5,0.5), (0.8,0.2) would all go into the same bucket.

Place all points into these buckets, then iterate over points again.

The reason for this organization is that you only need to check a point against the points in the same bucket, or in the 8 neighbouring buckets.

In a bad case this could still be O(n^2) (e.g. if all points are within t of each other), but it may help in some cases.