Veröffentlichung

Titel:

Shortest path to a segment and quickest visibility queries

AutorInnen:

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

Kategorie:

Artikel in Zeitschriften

erschienen in:

Journal of Computational Geometry, Vol. 7, No. 2, 2016, pp. 77-100

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.

Download:

Journal Website

BibTeX-Eintrag:

@article{, author = {Valentin Polishchuk and Esther M. Arkin and Alon Efrat and Christian Knauer and Joseph S. B. Mitchell and G{\"{u}}nter Rote and Lena Schlipf and Topi Talvitie}, title = {Shortest path to a segment and quickest visibility queries}, journal = {JoCG}, volume = {7}, number = {2}, pages = {77--100}, year = {2016}, }