Report B 05-05
We want to preprocess a simple $n$-vertex polygon $P$ to quickly determine the shortest path from a fixed source point $s \in P$ to some point visible from a query point $q \in P$. We call such queries inspection-path queries.We give an algorithm that computes a data structure which answers the queries in logarithmic time. The data structure has $O(n)$ size and can be computed in $O(n log n)$ time.
Get the report here or by anonymous ftp: Server: fubinf.inf.fu-berlin.de File: pub/reports/tr-b-05-05.pdf.gz