Geometric Visibility in Multiply Connected Domains

27 concepts22 papers1 proposal

In computational geometry, visibility problems answer a deceptively simple question: What can an observer see from a given point in space? When the environment is a simple polygon—a single, continuous boundary enclosing a region—the geometry behaves beautifully. Lines of sight are well-behaved, shortest paths are unique, and algorithms run efficiently.

However, real-world environments are rarely perfectly empty rooms; they contain pillars, walls, and obstacles. Mathematically, introducing these obstacles transforms a simple polygon into a multiply connected domain (a polygon with holes). This topological shift shatters the geometric assumptions that make simple polygon algorithms work, creating a profound complexity gap across visibility, pathfinding, and spatial optimization.

The Loss of Unique Shortest Paths

Why does adding a hole make visibility so much harder? The core reason lies in the topology of paths.

In a simple polygon, there is exactly one shortest path (a geodesic) between any two points. Because this path is unique, the polygon can be cleanly partitioned into visibility structures. As shown by Guibas et al. in Visibility and Intersection Problems in Plane Geometry, determining what a line of sight hits first relies on tracking the continuous space of lines that avoid boundaries.

When holes are introduced, the domain is no longer simply connected. Two points can now be connected by multiple, distinct shortest paths that wind around different sides of an obstacle. As Aronov et al. observe in Visibility Queries and Maintenance in Simple Polygons, many standard visibility algorithms rely entirely on this uniqueness property. Without it, decomposing a polygon into visibility regions becomes immensely complicated because light rays and shortest paths can split into different topological classes (homotopies). This challenge directly hinders the extension of Manhattan-distance shortest path queries, which Wang et al. note are heavily restricted by hole-free decompositions in L1 Shortest Path Queries in Simple Polygons.

The Shattering of Geodesic Convexity

In a simple polygon, proximity and visibility are tightly linked through the concept of geodesic neighborhoods (or "geodesic balls"). In a simple polygon, these balls are well-behaved: they exhibit a property known as P-convexity and have a Helly number of two. As proved by Bae et al. in Computing the L 1 Geodesic Diameter and Center of a Simple Polygon in Linear Time, these properties allow algorithms to find the geometric center or diameter of a polygon in linear time.

In a multiply connected domain, however, a geodesic ball expanding outward can hit a hole, wrap around it, and overlap itself. The authors later detailed in Computing the L1 geodesic diameter and center of a simple polygon in linear time that this causes the balls to lose their P-convexity, pushes the Helly number above two, and means the farthest neighbor from a point is no longer guaranteed to be a polygon vertex.

Similarly, divide-and-conquer strategies for geometric graphs often rely on the "pseudo-disk property," where the boundaries of geometric regions intersect at most twice. Within simple polygons, geodesic disks maintain this property, allowing for efficient clustering and separation. But as de Berg et al. show in Clique-Based Separators for Geometric Intersection Graphs, internal obstacles break the pseudo-disk property entirely. This prevents the use of standard separator-based algorithms for facility location and clustering in complex environments, a limitation also highlighted by de Berg et al. in Clustering in Polygonal Domains.

Combinatorial Explosion and Incompressibility

Can we bypass these topological issues by precomputing a visibility graph—a network connecting all pairs of mutually visible vertices?

For simple polygons, the answer is yes, because their visibility graphs are highly structured and compressible. However, Aronov et al. proved in Can Visibility Graphs Be Represented Compactly? that the moment you move to general disjoint segments (such as the boundaries of holes), visibility graphs become almost entirely incompressible, requiring near-quadratic space in the worst case. The continuous, un-fragmented boundary of a simple polygon is the exact feature that enables compact visibility representations.

This combinatorial explosion manifests dramatically when an observer moves. In a simple polygon, a moving viewpoint experiences a highly predictable sequence of visibility changes. But as Chen et al. explain in Maintaining Visibility of a Polygon with a Moving Point of View, introducing internal holes causes a massive surge in the complexity of visibility events and topological changes. A single obstacle can repeatedly occlude and reveal different parts of the scene, making dynamic tracking or weak visibility queries (determining what is visible from an entire line segment) vastly more complex, as noted by Chen et al. in Weak Visibility Queries of Line Segments in Simple Polygons.

This fragmentation of ray space mirrors challenges in computer vision. As Yu et al. describe in Multiperspective Projection and Collineation, when light rays do not originate from a single point, determining visibility and handling occlusions becomes significantly harder due to the complex geometry of the resulting ray manifolds. In a similar vein, the geometric interactions required to build skeletal structures become far less predictable; Huber et al. note in Approximating a Motorcycle Graph by a Straight Skeleton that a substantial gap remains in understanding the computational complexity of skeletons when moving from simple polygons to those with internal voids.

The Hardness of Spatial Guarding

This theoretical gap has severe practical consequences for spatial optimization problems, most notably the Art Gallery Problem (finding the minimum number of guards to oversee a polygon).

In hole-free environments, visibility regions are continuous enough that approximation algorithms can find near-optimal guard placements. But when holes are introduced, the problem undergoes a fundamental complexity shift. Bonnet et al. demonstrated in An Approximation Algorithm for the Art Gallery Problem that the presence of holes makes the point guard problem significantly harder, potentially escalating it to $W[2]$-hardness.

Because holes act as arbitrary occlusions, they force algorithms to handle intricate partitioning strategies. As Banerjee et al. point out in Vertex guarding for dynamic orthogonal art galleries, maintaining visibility coverage in dynamic settings with internal boundaries requires significantly more guards and complex geometric partitioning to account for these blind spots. This bottleneck is why modern exact algorithms, such as those proposed by Hengeveld et al. in A Practical Algorithm with Performance Guarantees for the Art Gallery Problem and later refined in their 2023 follow-up, remain explicitly constrained to hole-free polygons to preserve their performance guarantees.

Key Foundational Work

Visibility and Intersection Problems in Plane Geometry (1989) — contributed 1 concept elements to this direction.
Can Visibility Graphs Be Represented Compactly? (1994) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_multiply_connected_domain_visibility_267e4e04,
  title = {multiply-connected domain visibility},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/multiply-connected-domain-visibility/rdr_267e4e040b1e4f94b5187f740378fd8a},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_multiply_connected_domain_visibility_267e4e04_v1,
  title = {multiply-connected domain visibility},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/multiply-connected-domain-visibility/rdr_267e4e040b1e4f94b5187f740378fd8a/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake