Abstract
Let s be a point in a polygonal domain P of h1 holes and n vertices. We consider the following quickest visibility query problem. Given a query point q in P, the goal is to find a shortest path in P to move from s to see q as quickly as possible. Previously, Arkin et al. (SoCG 2015) built a data structure of size O(n^2 2^alpha(n) log n) that can answer each query in O(K log^2 n) time, where alpha(n) is the inverse Ackermann function and K is the size of the visibility polygon of q in P (and K can be Theta(n) in the worst case). In this paper, we present a new data structure of size O(n log h + h^2) that can answer each query in O(h log h log n) time. Our result improves the previous work when h is relatively small. In particular, if h is a constant, then our result even matches the best result for the simple polygon case (i.e., h = 1), which is optimal. As a byproduct, we also have a new algorithm for the following shortestpathtosegment query problem. Given a query line segment tau in P, the query seeks a shortest path from s to all points of tau. Previously, Arkin et al. gave a data structure of size O(n^2 2^alpha(n) log n) that can answer each query in O(log^2 n) time, and another data structure of size O(n^3 log n) with O(log n) query time. We present a data structure of size O(n) with query time O(h log n/h), which favors small values of h and is optimal when h = O(1).
BibTeX  Entry
@InProceedings{wang:LIPIcs:2017:7186,
author = {Haitao Wang},
title = {{Quickest Visibility Queries in Polygonal Domains}},
booktitle = {33rd International Symposium on Computational Geometry (SoCG 2017)},
pages = {61:161:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770385},
ISSN = {18688969},
year = {2017},
volume = {77},
editor = {Boris Aronov and Matthew J. Katz},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7186},
URN = {urn:nbn:de:0030drops71863},
doi = {10.4230/LIPIcs.SoCG.2017.61},
annote = {Keywords: shortest paths, visibility, quickest visibility queries, shortest path to segments, polygons with holes}
}
Keywords: 

shortest paths, visibility, quickest visibility queries, shortest path to segments, polygons with holes 
Collection: 

33rd International Symposium on Computational Geometry (SoCG 2017) 
Issue Date: 

2017 
Date of publication: 

20.06.2017 