Esther M. Arkin, Alon Efrat, Christian Knauer, Joseph S. B. Mitchell, Valentin Polishchuk, Günter Rote, Lena Schlipf, and Topi Talvitie:

Shortest path to a segment and quickest visibility queries

1. Journal of Computational Geometry 7 (2016), 77–100. Special issue for the 31st International Symposium on Computational Geometry (SoCG 2015). doi:10.20382/jocg.v7i2a5
2. In: 31st International Symposium on Computational Geometry (SoCG 2015), Eindhoven, June 2015. Editors: Lars Arge and János Pach, Leibniz International Proceedings in Informatics (LIPIcs), Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2015, pp. 658–673. doi:10.4230/LIPIcs.SOCG.2015.658
3. Christian Knauer, Günter Rote, and Lena Schlipf: Shortest inspection-path queries in simple polygons. In: Abstracts of the 24th European Workshop on Computational Geometry, Nancy, March 2008, pp. 153–156. (preliminary version of partial results from 1 and 2.) pdf file

Abstract

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.

Topi Talvitie has provided an interactive visualization of the visibility map for the problem.