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