Quickest Visibility Queries in Polygonal Domains

Haitao Wang

In computational geometry and robotics, finding the shortest path between two points is a fundamental task. However, many applications—such as a security guard spotting an intruder or a robot establishing a line-of-sight for communication—require reaching a point from which a target is visible, rather than reaching the target itself. This is known as the quickest visibility query.

Haitao Wang's 2017 paper presents a significant algorithmic advancement for this problem in complex 2D environments. By shifting the complexity dependency from the size of visibility polygons to the number of obstacles (holes) in a domain, the proposed method provides a much more efficient solution for environments that are not overly cluttered.

The Challenge of Polygonal Domains

A polygonal domain $\mathcal{P}$ consists of an outer boundary and $h-1$ holes, totaling $n$ vertices. Previous state-of-the-art methods had query times dependent on $K$, the number of vertices in the target's visibility polygon. Since $K$ can be as large as $n$, these queries could be very slow in complex environments.

Figure 2: A polygonal domain with holes (black) and visibility windows (red segments) used to determine line-of-sight.

The core objective is to make the query time independent of $K$ and more efficient for domains where the number of holes $h$ is small relative to the total number of vertices $n$.

Methodology: Decomposition and Pruning

The author achieves these bounds through several sophisticated geometric techniques:

1. Domain Decomposition

The domain is decomposed into $O(n)$ cells using $O(h)$ shortest paths from the source $s$ to specific vertices. This ensures that any line segment in the domain intersects at most $O(h)$ cells, facilitating faster traversal.

2. Path Bundles and Pruning

To solve the visibility problem, the algorithm must check "windows"—extensions of edges that define visibility. Instead of checking all $O(K)$ windows, the author introduces a pruning algorithm. It groups shortest paths into "bundles" and uses their geometric properties to eliminate windows that cannot possibly contain the quickest path.

Figure 1: A tree-like structure representing path bundles, where shared sub-paths are exploited for efficient pruning.

This "bundle" approach relies on the fact that shortest paths in these domains are "consistent" (they do not cross each other). Checking one path in a bundle can provide information about all other paths in that group, allowing for massive reductions in the search space.

3. Extended Corridor Structure

The paper utilizes an "ocean, bays, and canals" framework to partition the free space around holes. This reduces the set of candidate visibility windows from $O(K)$ down to a manageable $O(h)$.

Key Results and Performance

The primary result is a data structure for quickest visibility queries with the following characteristics:

  • Query Time: $O(h \log h \log n)$. This is a major improvement over the previous $O(K \log^2 n)$ when $h$ is small.
  • Space Complexity: $O(n \log h + h^2)$.
  • Optimality: When $h = O(1)$ (a constant number of holes), the query time becomes $O(\log n)$, which matches the best-known results for simple polygons.

Additionally, the paper provides a new algorithm for shortest-path-to-segment queries, achieving $O(h \log \frac{n}{h})$ query time with $O(n)$ space.

Conclusion and Future Directions

The most striking insight of this work is that the time to find the quickest path to see a target doesn't have to depend on the complexity of the target's view ($K$). By focusing on the topology of the holes ($h$), the algorithm provides a significant speedup for practical maps, like floor plans, where $h$ is typically much smaller than $n$.

Future work may address the $h^2$ dependency in space and preprocessing time, which could be prohibitive in extremely cluttered environments. Furthermore, extending these techniques to dynamic environments with moving sources or obstacles remains an open challenge for the robotics community.

Summary updated

BibTeX
@article{wang2019quickest,
  author = {Haitao Wang},
  title = {{Quickest Visibility Queries in Polygonal Domains}},
  journal = {Discret. Comput. Geom.},
  year = {2019},
  doi = {10.1007/s00454-019-00108-8},
}
Figure