Report B 05-05
April 2005
Abstract
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