TY - GEN
T1 - Visibility and intersection problems in plane geometry
AU - Chazelle, Bernard
AU - Guibas, Leonidas J.
N1 - Publisher Copyright:
© 1985 ACM.
PY - 1985/6/1
Y1 - 1985/6/1
N2 - We develop new data structure! for solving various visibility and intersection problems about a simple polygon P on n vertices. Among our results are a simple 0(nlog n) algorithm for computing the illuminated subpolygon of P from a luminous side, and an 0(log n) algorithm for determining which side of P is first hit by a bullet fired from a point in a certain direction. The latter method requires preprocessing on P which take time 0(n log n) and space 0(n). Our main new tool in attacking these problems is geometric duality on the two-sided plane.
AB - We develop new data structure! for solving various visibility and intersection problems about a simple polygon P on n vertices. Among our results are a simple 0(nlog n) algorithm for computing the illuminated subpolygon of P from a luminous side, and an 0(log n) algorithm for determining which side of P is first hit by a bullet fired from a point in a certain direction. The latter method requires preprocessing on P which take time 0(n log n) and space 0(n). Our main new tool in attacking these problems is geometric duality on the two-sided plane.
UR - http://www.scopus.com/inward/record.url?scp=85034590497&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85034590497&partnerID=8YFLogxK
U2 - 10.1145/323233.323252
DO - 10.1145/323233.323252
M3 - Conference contribution
AN - SCOPUS:85034590497
T3 - Proceedings of the 1st Annual Symposium on Computational Geometry, SCG 1985
SP - 135
EP - 146
BT - Proceedings of the 1st Annual Symposium on Computational Geometry, SCG 1985
PB - Association for Computing Machinery, Inc
T2 - 1st Annual Symposium on Computational Geometry, SCG 1985
Y2 - 5 June 1985 through 7 June 1985
ER -