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 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.
  pdf file (gzipped)
other papers about this subject
Last update: August 24, 2005.