TY - GEN
T1 - Determining sector visibility of a polygon
AU - Bhattacharya, B.
AU - Kirkpatrick, D. G.
AU - Toussaint, G. T.
N1 - Funding Information:
It remains now to show that the condition Q 5 1 in the two preceeding theorems cannot be relaxed. This is an immediate consequence of the following, This research reported here was supported in part by the National Science and Engineering Research Council. It results from collaboration during the third author’s tenure as a British Columbia Advanced Systems Institute Visiting Fellow.
PY - 1989/6/5
Y1 - 1989/6/5
N2 - We consider a generalization of notions of external visibility of simple polygons, namely weak external visibility, weak external visibility from a line and monotonicity, that we call sector visibility. Informally, sector visibility addresses the question of external visibility along rays (or sight lines) whose angles are restricted to a sector (wedge) of specified width u. This provides an interesting measure of the degree of external visibility of a polygon. Our framework also permits a unification and extension of a number of previously unrelated results. Finally, our results uncover a curious complexity discontinuity in this family of problems; algorithms are θ(n) when γ < φ or γ = 2φr, but require ω(n log n) time (at least), when φ < u < 2φ.
AB - We consider a generalization of notions of external visibility of simple polygons, namely weak external visibility, weak external visibility from a line and monotonicity, that we call sector visibility. Informally, sector visibility addresses the question of external visibility along rays (or sight lines) whose angles are restricted to a sector (wedge) of specified width u. This provides an interesting measure of the degree of external visibility of a polygon. Our framework also permits a unification and extension of a number of previously unrelated results. Finally, our results uncover a curious complexity discontinuity in this family of problems; algorithms are θ(n) when γ < φ or γ = 2φr, but require ω(n log n) time (at least), when φ < u < 2φ.
UR - http://www.scopus.com/inward/record.url?scp=0346928759&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0346928759&partnerID=8YFLogxK
U2 - 10.1145/73833.73860
DO - 10.1145/73833.73860
M3 - Conference contribution
AN - SCOPUS:0346928759
T3 - Proceedings of the Annual Symposium on Computational Geometry
SP - 247
EP - 254
BT - Proceedings of the 5th Annual Symposium on Computational Geometry, SCG 1989
PB - Association for Computing Machinery
T2 - 5th Annual Symposium on Computational Geometry, SCG 1989
Y2 - 5 June 1989 through 7 June 1989
ER -