Suppose there is a polygon with no holes and self-intersections (i.e. a simple polygon) defined by n vertices. Choose a reflex vertex v of this polygon.
I'd like to find any other vertex u of the same polygon which is "visible" from the vertex v. By visible I mean, that a line segment between v and u lies completely inside the polygon.
Is there an algorithm to do that in O(N) time or better? Is there an algorithm that can find all visible vertices in O(N) time?
A quick research suggests that for a given polygon and any point inside this polygon a visibility polygon can be constructed in O(N). I assume that finding a single visible vertex should be even easier.
This problem was solved 30 years ago:
ElGindy and Avis, "A linear algorithm for computing the visibility polygon from a point", J. Algorithms 2, 1981, p. 186--197.
There is a very nice paper by Joe & Simpson, 1985, "Visibility of a simple polygon from a point," that offers carefully verified pseudocode: (PDF download link). This surely has been implemented many times since, in many languages. For example, there is a link at the Wikipedia article on the topic.