2026-07-20T11:46:00Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5147 2024-03-06T10:35:55Z ddc:004 open_access

Shortest Path to a Segment and Quickest Visibility Queries Arkin, Esther M. Efrat, Alon Knauer, Christian Mitchell, Joseph S. B. Polishchuk, Valentin Rote, Günter Schlipf, Lena Talvitie, Topi path planning visibility query structures and complexity persistent data structures continuous Dijkstra 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Esther M. Arkin and Alon Efrat and Christian Knauer and Joseph S. B. Mitchell and Valentin Polishchuk and Günter Rote and Lena Schlipf and Topi Talvitie 2015 Is Part Of LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SOCG.2015.658 urn:nbn:de:0030-drops-51474 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.658 eng https://creativecommons.org/licenses/by/3.0/legalcode