Finding closest edge to a point in a planar graph

Question

I have a point location problem (in a planar graph) with a twist: rather then finding which region the point is located in, I would like to find the closest segment (edge) to a point, ideally with a O(log n) complexity.

So far I was not successful in finding any reference that would discuss this specific problem. Is there any treatment you know of?

For this problem, we can assume that the graph is embedded in a Euclidian plane in a known way, where vertices are mapped to points and edges are mapped to straight line segments.

Answer 1

Use a Voronoi diagram of the line segments

As @D.W. noted, a Voronoi diagram of line segments¹ is the usual way to approach this problem. It is possible to construct such a diagram via a modification of the Bentley-Ottman sweep-line algorithm for ordinary Voronoi diagrams (on points), see for example Section 7.3 of Computational Geometry by de Berg et al. But I don't think you should do this.

Don't use a sweepline algorithm

However, while sweep-line algorithms are nice in theory, implementing them in a robust and efficient manner turns out to be quite difficult in practice. I think this goes doubly so for the Bentley-Ottman algorithm. Therefore, in the field of algorithm engineering, which concerns itself with implementing algorithmic ideas on a computer, (randomized) incremental construction methods are usually preferred. These methods are much easier to make robust and are dynamic (support modifications efficiently) by default². The (expected) running time is also often not so bad in theory, and can beat the theoretically superior algorithm in practice. (if someone managed to implement the other algorithm effectively, that is).

Use random incremental construction

I recommend the algorithm by Karavelas (described in this conference paper ). It computes a line segment Voronoi diagram in $O((n+m)\log^2 n)$ expected time, together with a hierarchical structure that supports nearest neighbor queries in $O(\log^2 n)$ expected time. (Here, $n$ is number of segments, and $m$ the number of points)

This algorithm is implemented in the CGAL library, see this manual page for the details.

---

_{1: Formally, this is only a proper generalisation of a Voronoi diagram if the line segments are disjoint, because if the nearest point is point shared by two segments, we cannot uniquely determine its cell. If these line segments form the embedding of a planar graph, they only intersect at the end-points. In this case, we can often get away with shrinking the segments a tiny bit s.t. the endpoints are now disjoint. Another option is to consider the open segments and their endpoints as 3 separate objects, and make a Voronoi diagram of those.
2: More precisely, insertion is already implemented, and deletion is usually not too hard to add.}

Answer 2

I haven't tried to work out the details, but it seems plausible to me that it might be possible to solve this with a sweepline algorithm, with ideas from the Bentley-Ottman algorithm.

In particular, one approach would be to build the Voronoi diagram of the line segments (rather than a Voronoi diagram of points, as we usually do), then store it in a data structure that allows us to quickly query, given a point, which Voronoi cell it is contained in. A standard architecture for that with a sweepline algorithm is to move a vertical sweepline left to right, with an "event" for each point/vertex in the Voronoi diagram. At any point in time, we store the set of Voronoi edges sorted vertically in a binary search tree; we store all of these, one per event, using a persistent data structure.

I think the edges of that Voronoi diagram are composed of line segments and segments of a circle, all obtained by taking segments from (a subset of) the following possibilities:

• Given a pair of line segments AB and CD, there's a line equidistant between the two of them.

• Given a pair of line segments AB and CD, there's a parabolic arc that is equidistant between A and CD. (And symmetrically for B.)

And I think all of the vertices of the Voronoi diagram are composed of intersections between the following constructed lines:

• Given a pair of line segments AB and CD, consider the line equidistant between them.

• Given a line segment AB, consider the line that is perpendicular to AB and goes through A. (And symmetrically for B.)

So, I think it might be possible to identify all of the vertices of the Voronoi diagram by using a sweepline algorithm based on Bentley-Ottman to construct all of those intersections; then use a persistent data structure based on a sweepline with one event per vertex, where we use the persistent binary tree to represent the Voronoi cells that intersect with the sweepline.

You would need to check the details. I haven't tried to work through all of this to see if it can actually be made to work or if there are some difficulties I'm overlooking right now.

Possibly also useful: https://gis.stackexchange.com/q/104631, https://mathoverflow.net/q/311592/37212, https://www.cosy.sbg.ac.at/~held/projects/vroni/vroni.html, http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.95.2920&rep=rep1&type=pdf