Building vertex-edge visibility graph among polygonal obstacles on 2d plane

Question

I want to implement algorithm for computing vertex-edge visibility graph among polygonal obstacles, but I can't find any description or scientific paper describing such algorithm. Currently I understand how to extend Lee's algorithm for vertex-vertex visibility graph to compute vertex-edge graph, but I want to achieve better than $O(n^2 log(n))$ complexity. I read paper of Mount and Ghosh about their $O(nlog(n))$ algorithm based on triangulation of free space, and seems it allows extension to produce vertex-edge graph. But that algo has too complicated implementation :)

I wonder if there is a way to extend Overmars and Welzl algorithm $O(n^2)$ or algorithm with similar complexity to produce vertex-edge visibility graph? It's implementation seems to be quite simple. Point me on some papers, links, or describe it here if you can.

Answer 1

I'm not sure if this is what you're after, but here's an $O(n + k)$ approach from J. O'Rourke and I. Streinu, Computational Geometry 10 (1998), pp. 105-120:

$G_{VE}$ may be constructed in $O(n + k)$ time for a polygon with $n$ vertices and $k$ visibility edges, by a slight modification of Hershberger's algorithm that constructs $G_v$ in this time bound [8] from a polygon triangulation. Supplementing with Chazelle's linear-time triangulation algorithm achieves the claimed bound.