Faster ways to search points close to a line

Question

I have a set of points and a line in 2D space. I need to find all points that lie within a distance D from the line. Is there a way for me to do this without having to actually compute distances di of all points from the line? Is there a solution better than linear search?

Edit: I need to search through the same point set for different lines multiple times. The points are always constant but the line would be different during each search. Typically the point set is of the order of tens of thousands (~50k).

Answer 1

As for queries:

If you create a kd-tree using the points, and use a few equidistant points (likely around d) points on the line, you should be able use a modifed nearest neighbor query to find all points that are withing d of a line in roughly O(k + log(N)). The kd-tree requires O(N log N) preprocessing through, so it's only better if you use the same point set (with perhaps slight differences as you can add/remove a point from a kd-tree in O(log N)) and different lines. The only issue is that a kd-tree isn't really meant for use with lines. I'm sure there is something like it for lines that would work better, but I'm not familiar with it.

Note: False positives and negatives are possible depending on how things are arranged, as you are really querying the distance from a point on the line instead of the distance on the line. How problematic this is largely depends on the ratio between the length of the line and d. Thus you are either going to get a fair number false positives or false negatives unless the majority of the points are no where near the line. In general, this probably won't be too much of an issue though, as even with the false positives k should be fairly small compared to N unless d is relatively large.

After a bit of review, I noticed that the query is against a line not line segment. It can however be converted into one by make the line segment bounded by the min/max x/y. I imagine there is still probably a more efficent way to use a kd-tree for this.

Answer 2

This search can't be completed faster than linear search, as input data and result population has the same complexity.