License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2017.61
URN: urn:nbn:de:0030-drops-71863
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7186/
Go to the corresponding LIPIcs Volume Portal

Wang, Haitao

Quickest Visibility Queries in Polygonal Domains

pdf-format:
LIPIcs-SoCG-2017-61.pdf (0.6 MB)

Abstract

Let s be a point in a polygonal domain P of h-1 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 by-product, we also have a new algorithm for the following shortest-path-to-segment 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:1--61:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Boris Aronov and Matthew J. Katz},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7186},
  URN =		{urn:nbn:de:0030-drops-71863},
  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

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI