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.


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.

  pdf file (gzipped)
other papers about this subject
Last update: March 31, 2008.