Published on *Computer Science Department at Princeton University* (http://www.cs.princeton.edu)

We develop new data structures for solving various visibility and intersection problems about a simple polygon P on n vertices. Among our results are a simple O(n log n) time algorithm for computing the illuminated subpolygon of P from a luminous side, and an O(log n) time 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 takes time O(n log n) and space O(n). The two main tools in attacking these problems are geometric duality on the two-sided plane and fractional cascading.

**Links**

[1] http://www.cs.princeton.edu/research/techreps/author/283

[2] http://www.cs.princeton.edu/research/techreps/author/417

[3] ftp://ftp.cs.princeton.edu/techreports/1988/167.pdf