@inproceedings{861705ff52034f6683600454e8c50076,

title = "Visibility and intersection problems in plane geometry",

abstract = "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.",

author = "Bernard Chazelle and Guibas, {Leonidas J.}",

year = "1985",

month = jun,

day = "1",

doi = "10.1145/323233.323252",

language = "English (US)",

series = "Proceedings of the 1st Annual Symposium on Computational Geometry, SCG 1985",

publisher = "Association for Computing Machinery, Inc",

pages = "135--146",

booktitle = "Proceedings of the 1st Annual Symposium on Computational Geometry, SCG 1985",

note = "1st Annual Symposium on Computational Geometry, SCG 1985 ; Conference date: 05-06-1985 Through 07-06-1985",

}