Shortest path to a segment and quickest visibility queries

Esther M Arkin, Alon Efrat, Christian Knauer, Joseph SB Mitchell, Valentin Polishchuk, Günter Rote, Lena Schlipf, Topi Talvitie


We show how to preprocess a polygonal domain with a fixed starting point $s$ in order to answer efficiently the following queries: Given a point $q$, how should one move from $s$ in order to see $q$ as soon as possible? This query resembles the well-known shortest-path-to-a-point query, except that the latter asks for the fastest way to reach $q$, instead of seeing it. Our solution methods include a data structure for a different generalization of shortest-path-to-a-point queries, which may be of independent interest: to report efficiently a shortest path from $s$ to a query segment in the domain.

Full Text:



ISSN: 1920-180X