# Compute visible vertices of a polygon

Given a simple polygon $P$ and a point $p$ within the polygon, I want to compute the vertices of $P$ visible from point $p$. A point $q$ is visible from point $p$, if the line segment $\overline{qp}$ is completely in the polygon $P$.

One can use the accepted answer here to compute visible vertices in $P$ from a point $p$ in $\mathcal{O}(n\log{}n)$.

My question is, does an algorithm exist to do it in $\mathcal{O}(n)$ time?

Yes, there are more algorithms to do so in $\mathcal O(n)$. The first is dated back to ElGindy and Avis in 1981, Lee 1983 and Joe & Simpson in 1985. The visibility algorithms use stack (the first one three stacks, further only one) and process vertices in order they appear at boundary.