@inproceedings{5b01d00ad68d412e834e123300e85367,
title = "Shortest Path to a Segment and Quickest Visibility Queries",
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.",
keywords = "Continuous Dijkstra, Path planning, Persistent data structures, Query structures and complexity, Visibility",
author = "Arkin, {Esther M.} and Alon Efrat and Christian Knauer and Mitchell, {Joseph S.B.} and Valentin Polishchuk and G{\"u}nter Rote and Lena Schlipf and Topi Talvitie",
year = "2015",
month = jun,
day = "1",
doi = "10.4230/LIPIcs.SOCG.2015.658",
language = "English (US)",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
pages = "658--673",
editor = "Janos Pach and Janos Pach and Lars Arge",
booktitle = "31st International Symposium on Computational Geometry, SoCG 2015",
note = "31st International Symposium on Computational Geometry, SoCG 2015 ; Conference date: 22-06-2015 Through 25-06-2015",
}