| Shortest Inspection-Path Queries in Simple Polygons (2009) | |||||||||||||||
Abstract | |||||||||||||||
| Abstract. We want to preprocess a simple n-vertex polygon P to quickly determine the shortest path p from a fixed source point s ∈ P to view a set Q ⊆ P of query points (i.e., such that each point q ∈ Q is visible from some point on the path p). We call such queries shortest inspection-path queries. For |Q | ≤ 2 we describe data structures that answer such queries in logarithmic time. The structures have linear (for |Q | = 1) respectively quadratic (for |Q | = 2) size and preprocessing time. For |Q | = 2 we also present a data structure with linear preprocessing time and space which achieves for any ɛ> 0 a query time of O ( 1 ɛ2 log n) at the expense of providing only a (1 + ɛ)-approximate answer. | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||