Christian Knauer, Günter Rote, and Lena Schlipf:
Shortest inspection-path queries in simple polygons
In: Abstracts of the 24th European Workshop on Computational Geometry,
Nancy, March 2008, pp. 153-156.
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 linear time. For shortest inspection
paths to two query points, the queries can be answered in logarithmic time,
using quadratic space and quadratic preprocessing time.
Last update: March 31, 2008.