Christian Knauer and Günter Rote:
Shortest inspection-path queries in simple polygons
Technical report B-05-05, April 2005, 6 pages.
We preprocess a simple polygon P to quickly determine the
a fixed source point in P to some point visible from a query
in P. For a polygon with n vertices, our data
inspection-path queries in logarithmic time, has linear size, and can
in O(n log n) time.
Last update: August 24, 2005.