Nearest point to set of line segments

Question

I have a point p, and n line segments in the 2d space. Is there a way I can preprocess the line segments so that I can efficiently (i.e. sublineraly) find the line segment closest (i.e with lowest perpendicular distance) to P?

This is a real-world problem we're trying to solve. The best (approximate) answer we have is to preprocess the ends of the line segments of the points into a quad tree/2d kd tree, and find the nearest point. This should lead to a nearly optimal answer (or maybe even correct answer) in most cases.

Alternately one can use Mongodb's geonear, which works with points as well.

Can we do better than this, particularly in terms of accuracy?

Toxic

The theoretical solution is to pre-build the Voronoi diagram of the segments, which is made of line segments and parabolic arcs and defines a subdvision of the plane. Then point location in a planar subdivision can be performed in optimal logarithmic time. But this solution is very difficult to implement. – Chuch

I read up on voronoi diagrams and parabolic arcs. It indeed solves the problem, but is fiendishly difficult to implement, as you stated. Is there a simpler way to solve the problem if the segments are connected? That is, it is a series of points p0...pn, and the line segments are p0-p1, p1-p2,...,pn-1 - pn? – Toxic

No, there is not. – Chuch

Answer 1

If your segments are uniformly spread and not too long, you can think of a gridding approach: choose a cell size and determine for every cell which segment crosses it (this is done by "drawing" the segments on the grid). Then for a query point, find the nearest non-empty cell, by visiting neighborhoods of increasing size, and compute the exact nearest distance to the segment(s) so found. You need to continue the search as long as the distance between the query point and the next cells does not exceed the shortest distance found so far.

If the distribution is not uniform, a quad-tree decomposition can be better.

---

More generally, a suitable strategy is to use any acceleration device that quickly will report a small number of candidate segments, with a guaranty: the nearest segment must be among the candidates.

Chuch