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.


1 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.

  • $\begingroup$ Sorry, I forgot to mention that I need this algorithm to run on a set of polygonal obstacles, not on one polygon. $\endgroup$
    – Bad Name
    Jul 13, 2017 at 8:03
  • 1
    $\begingroup$ Note that Chazelle's algorithm, while nice in theory, is difficult to implement and quite likely not that useful in practice. $\endgroup$
    – Discrete lizard
    Jul 13, 2017 at 11:09

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.