3
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ Welcome to COMPUTER SCIENCE @SE. I have an idea of an edge in a graph, and of a planar graph, but that is topology rather than geometry. What does closest [edge] to a point mean? What will be the input? Shall multiple queries be supported? $\endgroup$ – greybeard Sep 29 '20 at 7:08
  • $\begingroup$ @greybeard Yes, sorry about my sloppiness. For the purpose of my question one can assume that the graph is embedded in a plane in a known way (i.e. all vertices and edges have unique mapping to objects on a plane). Functions to compute distances are provided. One can furthermore assume that we are talking about Euclidean space. $\endgroup$ – MrMobster Sep 29 '20 at 7:42
3
$\begingroup$

Use a Voronoi diagram of the line segments

As @D.W. noted, a Voronoi diagram of line segments1 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 default2. 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.

$\endgroup$
4
  • $\begingroup$ Thank you, this seems promising! The weakly intersecting segments are not a problem for me — if a point is equidistant to multiple segments, any of them can be picked. One point from the paper I don't understand however: "if sites are allowed to weakly intersect the bisectors can become two-dimensional" (p.3). What do they mean by it? $\endgroup$ – MrMobster Sep 30 '20 at 13:51
  • $\begingroup$ @MrMobster A bisector between two segments is the region of points with equal distance to both segments. If the segments weakly intersect or don't intersect at all, this region can always be represented by a 1-d curve (not always a line! It can be a parabola or line-segments joined to a parabolic arc). If the segments strongly intersect, the bisector of the two segments can no longer be represented as a 1-d curve, as there are more than 2 outgoing arcs in the bisector that leave the intersection point of the segments. $\endgroup$ – Discrete lizard Sep 30 '20 at 15:40
  • $\begingroup$ I understand the problem with strong intersections, but the paper seems to suggest that weak intersections are also problematic. I can't imagine a case for example where a bisector of two segments that share an endpoint wouldn't be a line... $\endgroup$ – MrMobster Sep 30 '20 at 16:05
  • $\begingroup$ @MrMobster Ah. I think that is probably a mistake on their part. On page 2 the author states "When we allow the input segments to intersect at their interior ... [then] the bisectors are no longer homeomorphic to a line", which implies weak intersections are fine. I'm also fairly certain that the bisector of two weakly intersecting segments is just a line. $\endgroup$ – Discrete lizard Sep 30 '20 at 16:37
2
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ Thanks for the pointers, VD of line segments appears to be a very good place to start digging. Unfortunately, after looking at some literature, it seems that constructing it (and doing point location) is a bit more tricky and might be too complex to my use case. But I think one can use an approximation of a VD to build a region data structure that partitions the segments into "buckets" such that every region has up to N segments closest to it. $\endgroup$ – MrMobster Sep 30 '20 at 5:40
  • $\begingroup$ You don't really go into the details of doing the actual nearest neighbour query in this answer. For completeness, I suppose you want to do this with point location on the Voronoi diagram via a trapeziodal decomposition ? $\endgroup$ – Discrete lizard Sep 30 '20 at 7:09
  • $\begingroup$ @Discretelizard, yeah, good point, there are several areas that are awfully vague and handwavy. Basically, but it's worse than that: you have curved lines (segments of a circle), too. $\endgroup$ – D.W. Sep 30 '20 at 8:28
  • $\begingroup$ @D.W. Aren't the curved lines parabolic arcs? (i.e. they are sections of the equidistant region between a line and a point) But that sounds troublesome, as it seems the arcs may intersect multiple trapezoids if we pretend the arcs are segments when we construct the decomposition. Maybe point location with a hierarchical construction on the dual would be easier. $\endgroup$ – Discrete lizard Sep 30 '20 at 12:34
  • $\begingroup$ @Discretelizard, oops. Yes, you are right, parabolic arc, not a circle. Thank you. That's why I don't think a trapezoidal decomposition is enough; you have cells that are bounded by lines and by segments of a parabolic arc. I think you can still represent it in a persistent data structure with a sweepline algorithm (I think) and do efficient point location queries. But maybe sweepline approaches are not a good choice in practice for the reasons you articulate. $\endgroup$ – D.W. Sep 30 '20 at 19:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.