Quickest visibility queries in polygonal domains

DOI10.1007/S00454-019-00108-8MaRDI QIDQ2316797zbMATH OpenOpenAlexWikidataFDO

Authors Haitao Wang

Publication date 7 August 2019

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

Full work available at URL https://arxiv.org/abs/1703.03048, https://drops.dagstuhl.de/opus/volltexte/2017/7186/

Mathematics Subject Classification ID

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

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)$.

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

Cites work

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

Cited in

(10)

• Visibility queries in a polygonal region
• A new algorithm for Euclidean shortest paths in the plane
• 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)