Quickest visibility queries in polygonal domains

DOI10.1007/S00454-019-00108-8zbMATH Open1425.68441arXiv1703.03048OpenAlexW2952603777WikidataQ127665634 ScholiaQ127665634MaRDI QIDQ2316797FDOQ2316797

Authors: Haitao Wang 

Publication date: 7 August 2019

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Abstract: Let $s$ be a point in a polygonal domain $mathcalP$ of $h-1$ holes and $n$ vertices. We consider a quickest visibility query problem. Given a query point $q$ in $mathcalP$, the goal is to find a shortest path in $mathcalP$ 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)}logn)$ that can answer each query in $O(Klo{g}^{2}n)$ time, where $alpha(n)$ is the inverse Ackermann function and $K$ is the size of the visibility polygon of $q$ in $mathcalP$ (and $K$ can be $Theta(n)$ in the worst case). In this paper, we present a new data structure of size $O(nlogh+h^2)$ that can answer each query in $O(hloghlogn)$ 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 a shortest-path-to-segment query problem. Given a query line segment $au$ in $mathcalP$, the query seeks a shortest path from $s$ to all points of $au$. Previously, Arkin et al. gave a data structure of size $O(n^2{2}^{alpha(n)}logn)$ that can answer each query in $O(lo{g}^{2}n)$ time, and another data structure of size $O(n^{3}logn)$ with $O(logn)$ query time. We present a data structure of size $O(n)$ with query time $O(hlogfracnh)$, which also favors small values of $h$ and is optimal when $h=O(1)$.

Full work available at URL: https://arxiv.org/abs/1703.03048

Recommendations

• Quickest visibility queries in polygonal domains
• Visibility queries in a polygonal region
• Shortest path to a segment and quickest visibility queries
• Shortest path to a segment and quickest visibility queries
• Visualizing quickest visibility maps

Mathematics Subject Classification ID

Data structures (68P05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cites Work

• Title not available (Why is that?)
• Computational geometry. Algorithms and applications.
• Optimal Search in Planar Subdivisions
• Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
• An efficient algorithm for Euclidean shortest paths among polygonal obstacles in the plane
• Fast Algorithms for Finding Nearest Common Ancestors
• Optimal Point Location in a Monotone Subdivision
• An Optimal Algorithm for Euclidean Shortest Paths in the Plane
• SHORTEST PATHS AMONG OBSTACLES IN THE PLANE
• Topologically sweeping visibility complexes via pseudotriangulations
• A Pedestrian Approach to Ray Shooting: Shoot a Ray, Take a Walk
• THE VISIBILITY COMPLEX
• Ray shooting in polygons using geodesic triangulations
• Efficient visibility queries in simple polygons
• Visibility and ray shooting queries in polygonal domains
• A nearly optimal algorithm for finding \(L _{1}\) shortest paths among polygonal obstacles in the plane
• Shortest Paths Help Solve Geometric Optimization Problems in Planar Regions
• Computing the visibility polygon of an island in a polygonal domain
• \(L_1\) shortest path queries among polygonal obstacles in the plane
• TRIANGULATING DISJOINT JORDAN CHAINS
• A new algorithm for shortest paths among obstacles in the plane
• Optimal Shortest Path and Minimum-Link Path Queries between Two Convex Polygons inside a Simple Polygonal Obstacle
• Geometric k Shortest Paths
• Shortest path to a segment and quickest visibility queries

Cited In (9)

• Visibility queries in a polygonal region
• Visualizing quickest visibility maps
• Quickest visibility queries in polygonal domains
• Query-points visibility constraint minimum link paths in simple polygons
• Shortest Path Queries in Polygonal Domains
• Shortest path to a segment and quickest visibility queries
• Visibility and Ray Shooting Queries in Polygonal Domains
• Querying two boundary points for shortest paths in a polygonal domain
• Visibility queries and maintenance in simple polygons

This page was built for publication: Quickest visibility queries in polygonal domains

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2316797)