Efficient algorithm to find closest line segments for each point

Question

Given a polygonal subdivison S and a set of points P, find the closest line segment in S for each point (in 2-d space).
In my setting, I have hundreds of thousands of segments and a couple thousand points.

Checking each line for each point would take too long. Is there an efficient algorithm for this?

I was considering multiple options, but can't figure out which is best.

1. Build a trapezoidal map and query the face each point is in. Then go over the edges of the face (in the subdivision) to find the nearest line.
2. Build a range tree or segment tree. Query a box around the point and find the closest line segment in it. There has to be a segment in the box for this to find anything.
3. Build a line segment voronoi diagram. Each face describes the nearest segment, but I wouldn't know how to do a point query, since the edges can be parabolic arcs.

What is a good high-level approach for this problem?

Answer 1

Nearest Neighbor in Postgis

The approach of Postgis is to use R-trees with a custom search algorithm. While going down the tree like in a regular query, they keep track of the minimum and maximum distance to objects in the bounding regions they encounter in the tree. Each encountered branch of the tree is added to an Active Branch List (ABL), which are pruned using the distance metrics.

They pick a branch's bounding region in the ABL and apply the algorithm recursively. At a leaf (an object like a line segment), it updates the variable nearest. When returning from the recursion, they apply the nearest variable for more pruning of the ABL, repeating until the ABL is empty.

The theoretical worst case is linear per query, but it has much better results in practice.