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 -