Abstract
This paper introduces a formal framework for "local complexity" in simple polygons using two new metrics: Point Visibility Width ($pvw$) and Chord Visibility Width ($cvw$). While global parameters like the total number of reflex vertices are common in computational geometry, local complexity captures how "crowded" a polygon appears from a specific internal vantage point. The authors demonstrate that while a chord can see exponentially more reflex vertices than any single point, these measures remain combinatorially bounded. This work provides a foundation for parameterized geometric algorithms that scale with local simplicity rather than total vertex count.
Introduction
In computational geometry, the efficiency of algorithms often depends on the "simplicity" of the input shape. For instance, many problems are trivial for convex polygons but become significantly harder as the number of reflex vertices—the "dents" where internal angles exceed $180^\circ$—increases. However, global counts of reflex vertices do not always capture the practical difficulty of a shape. A polygon might have many reflex vertices globally but appear very simple from any local perspective.
This paper addresses the lack of a formal definition for local complexity. By quantifying how much of a polygon's complexity is visible from a single point or a single line segment (chord), the authors enable the development of "parameterized" algorithms. These algorithms can perform optimally on shapes that are locally simple, regardless of their total number of vertices.
Defining Local Complexity
The authors propose two primary measures for local complexity based on visibility within a simple polygon:
- Point Visibility Width ($pvw$): The maximum number of reflex vertices visible from any single point $p$ inside the polygon.
- Chord Visibility Width ($cvw$): The maximum number of reflex vertices visible from any single chord (a line segment connecting two boundary points).
Reflex vertices are chosen as the fundamental unit of complexity because they act as the primary obstacles to visibility and are the source of geometric "trouble" in most spatial algorithms.
The Relationship Between Point and Chord Visibility
A central contribution of the paper is exploring the relationship between these two widths. Intuitively, a chord should see more than a point because it is a collection of points. The authors quantify this gap using two distinct approaches.
The Iterated Comb Construction
To establish a lower bound, the authors designed a fractal-like "Iterated Comb" polygon. In this construction, a single chord can see a massive number of reflex vertices, while any individual point on that chord sees only a small, constant number. This demonstrates an exponential gap: the authors prove that $cvw$ can be $2^{\Omega(pvw)}$.
Combinatorial Linking
Despite this potential for an exponential difference, the authors prove that the two measures are still mathematically linked. Using Visibility Restriction Graphs—directed graphs where edges represent how one reflex vertex blocks the view of another—they establish an upper bound. They show that for any simple polygon, $cvw \leq pvw^{O(pvw)}$. This confirms that if a polygon is locally simple from the perspective of points, it cannot be infinitely complex from the perspective of chords.
Key Results and Algorithmic Impact
The primary theoretical result is summarized in Theorem 1: $$pvw \leq cvw \leq pvw^{O(pvw)}$$
This relationship has immediate implications for classic problems like the Art Gallery Problem (finding the minimum number of guards to see the entire interior). Recent research has shown that this problem is Fixed-Parameter Tractable (FPT) when $cvw$ is small. By formalizing these widths, the authors provide a rigorous way to categorize which polygons are "easy" for such problems.
Conclusion and Future Work
While this paper establishes the theoretical bounds of local complexity, several open questions remain. A key challenge is developing efficient algorithms to compute or approximate $pvw$ and $cvw$ for a given polygon. Currently, these are theoretical parameters; practical application in geometry engines would require fast calculation methods. Additionally, the authors suggest exploring alternative definitions of local complexity based on different geometric properties, such as link distance or the spatial distribution of vertices.
Summary updated