Notice removed Authoritative reference needed by Community
Bounty Ended with no winning answer by Community
3 edited title

# Algorithm to build Building vertex-edge visibility graph among polygonal obstacles on 2d plane

2 added 25 characters in body

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.

I want to implement algorithm for computing vertex-edge visibility graph., 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.

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.

Notice added Authoritative reference needed by Ibraim Ganiev
Bounty Started worth 100 reputation by Ibraim Ganiev
I want to implement algorithm for computing vertex-edge visibility graph., 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.