# Finding the closest visible vertex among line segments

Given a set $$S$$ of line segments (possibly sharing endpoints) and a query point $$q$$, how fast can we find the closest visible endpoint from $$q$$? If $$p$$ is the closest visible endpoint to $$q$$, then, in this case, it means that the line segment $$pq$$ does not intersect with any other line segment in $$S$$.

I am trying to implement an efficient algorithm in CGAL. I have explored the nearest-neighbor and visibility structures from CGAL but could not conclude anything.

• Please look for "2D Segment Voronoy Diagrams" – HEKTO Aug 21 '19 at 16:58

## 1 Answer

I only noticed after posting that my first answer does not directly address your specific question. So now my answer is in two parts.

(1) As suggested by @HEKTO, to find the closest segment, you could first compute the Voronoi diagram: CGAL 2D Segment Voronoi Diagrams. Then next you need to perform point location within the (non-rectilinear) cells of the diagram. That is also discussed, using "the segment Voronoi diagram hierarchy, a data structure suitable for fast nearest neighbor queries..." CGAL figure.

(2) You specifically ask for the closest segment endpoint, which is not necessarily an endpoint of the closest segment: Point $$x$$ is closer to segments $$1,2,3,4$$ than to the closest endpoint $$y$$.
For this you might need to look at "visibility constrained Voronoi diagrams":

Aurenhammer, Franz, Bing Su, Y-F. Xu, and Binhai Zhu. "A note on visibility-constrained Voronoi diagrams." Discrete applied mathematics 174 (2014): 52-56. Elsevier link.

I haven't studied this paper enough to be certain it solves your problem. And perhaps there is a way to efficiently move from the closest segment to the closest segment endpoint.

• Thank you. I was expecting something from CGAL which I can use right away. But it appears that there is none. – aghost Aug 22 '19 at 1:10