An Optimal Algorithm Computing Edge-to-Edge Visibility in a Simple Polygon
Mikkel Abrahamsen · 2013
Let P be a simple polygon with n vertices. We present a new O(n)-time algorithm to compute the visible part of one edge from another edge of P. The algorithm does not alter the input and only uses O(1) variables and is therefore a constant-workspace algorithm. The algorithm can be used to make a constant-workspace al-gorithm for computing the weak visibility polygon from an edge in O(mn) time, where m is the number of ver-tices of the resulting polygon, and a constant-workspace algorithm for computing a minimum link path between two points inside a simple polygon in O(n2) time. 1