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
-
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
-
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
-
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.
Last update: August 15, 2016.