Given a concave polygon $P$ defined by $n$ vertices and a point $p$ outside the polygon, I want to compute which of the vertices $v$ of the polygon are visible to point $p$. A vertex $v$ is considered visible to $p$ if the line between $p$ and $v$ doesn't cross the polygon $P$ in any edge or vertex except $v$. My current approach is to draw line segment from $p$ to each $v$ and check if that line intercepts any of the edges of the polygon $P$. Obviously this is quite a slow approach with $O(n^2)$, not to mention 2 line segment interception isn't a light computation. My question is if there is a faster approach to this problem, maybe in $O(n)$. This image should give a clear understanding of the problem. EDIT: I have found an optimization to this problem. Still using line segment intersections but first pruning some vertices that we know for sure won't be visible. Using the average coordinates of $P$, called $Center$ in the figure, we can calculate in $O(n)$ which vertices make a "bigger" angle with the $Center$ in relation to $q$. These vertices are $M$ and $T$ in the image. With this we can assume all the vertices "behind" $M$ and $T$ wont be visible to $q$ and that the edges that they form will also not interfere. This allows us to "prune" a good amount of vertices and cutting the temporal complexity of the problem a lot. Unfortunately, in the worst case this will only save us from checking one edge meaning the complexity will still be $O(n^2-n)$. But it can also cause the best case to be $O(n)$. So in the general case, given a concave polygon with vertices well distributed we should expect around $O(n log(n))$ complexity with this optimization. That's pretty good already. However now I'm wondering if it's possible to use this idea of rays further and really get a solution that is always $O(n log(n))$ or even $O(n)$... Login To add answer/comment