In the conference paper Approximation Algorithms for Shortest Path Motion Planning, by K.L. Clarkson, the author claims in section 3 that, by using planar point location on conical Voronoi diagrams (defined in the paper), the construction of a $\theta$-graph (or any 'cone-based spanner') that does not intersect polygonal obstacles can be done in $O(n\log n)$ time, where $n$ is the amount of vertices in the graph (the obstacle vertices are included). I can see that the construction of the conical Voronoi diagram can indeed be done in $O(n\log n)$ with a variant of Fortune's algorithm. I do not see how this prevents intersection with the polygonal obstacles, however. I'd like to know how this can be done, or if you believe this approach is unlikely to work, I'd like to see some reasoning why this is the case.I found the explanation of conical Voronoi diagrams in the paper is rather confusing (and the illustration only increased my confusion), but my interpretation is that it is simply a 'normal' Voronoi diagram, but uses the 'conical distance' for a given cone instead of the Euclidian distance. Please correct me if this interpretation is wrong.Some 'meta' details: The 'paper' states that the full algorithm will be explained in detail in the 'full version'. However, I do not think this full version exists, as I am unable to find it in citation databases and the only related citation cites the conference paper (and this resource neither explains nor requires the claimed running time). This makes me a bit skeptical about the claimed results of the technique.I'm very much interested whether this technique works both theoretically and practically, as I have approached the same problem with different techniques, but got a running time of $O(n\log n)$ only under the special case of a bounded number of convex polygonal obstacles.
How do Clarkson's conical Voronoi diagrams avoid intersections?
algorithms;data structures;computational geometry