Shortest Inspection-Path Queries in Simple Polygons

Christian Knauer
Institut für Informatik
Freie Universität Berlin
Takustr. 9, 14195 Berlin
email: knauer@mi.fu-berlin.de

Günter Rote
Institut für Informatik
Freie Universität Berlin
Takustr. 9, 14195 Berlin
email: rote@mi.fu-berlin.de

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