Shortest inspection-path queries in simple polygons

Abstract

We want to preprocess a simple n-vertex polygon P to quickly determine the shortest path from a fixed source point s 2 P to some point visible from a query point q 2 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.