An optimal algorithm computing edge-to-edge visibility in a simple polygon

TY - GEN

T1 - An optimal algorithm computing edge-to-edge visibility in a simple polygon

AU - Abrahamsen, Mikkel

N1 - Conference code: 25

PY - 2013

Y1 - 2013

N2 - Let P be a given, 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 constantworkspace algorithm for computing the weak visibility polygon from an edge in O(mn) time, where m is the number of vertices 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.

AB - Let P be a given, 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 constantworkspace algorithm for computing the weak visibility polygon from an edge in O(mn) time, where m is the number of vertices 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.

M3 - Article in proceedings

SP - 157

EP - 162

BT - Proceedings of the 25th Canadian Conference on Computational Geometry

T2 - Canadian Conference on Computational Geometry 2013

Y2 - 8 August 2013 through 10 August 2013

ER -