1990
An Optimal Algorithm for Detecting Weak Visibility of a Polygon
Publication
Publication
IEEE Transactions on Computers , Volume 39 - Issue 10 p. 1213- 1219
In 1981, Avis and Toussaint gave a linear-time algorithm for the following problem. Given a simple n-Vertex polygon P and an edge of P, determine whether each point in P can be seen by some (not necessarily the same) point on the edge. They posed the more general problem of finding a subquadratic algorithm for determining whether such an edge exists. In this paper, we present a linear-time algorithm for determining all (if any) such edges of a given simple polygon.
| Additional Metadata | |
|---|---|
| Algorithms, computational complexity, computational geometry, visibility | |
| dx.doi.org/10.1109/12.59852 | |
| IEEE Transactions on Computers | |
| Organisation | School of Computer Science |
|
Sack, J.-R, & Suri, S. (Subhash). (1990). An Optimal Algorithm for Detecting Weak Visibility of a Polygon. IEEE Transactions on Computers, 39(10), 1213–1219. doi:10.1109/12.59852
|
|