Local Complexity of Polygons

Fabian Klute, Meghana M. Reddy, Tillmann MiltzowarXiv 2021 · arXiv

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:

  1. Point Visibility Width ($pvw$): The maximum number of reflex vertices visible from any single point $p$ inside the polygon.
  2. Chord Visibility Width ($cvw$): The maximum number of reflex vertices visible from any single chord (a line segment connecting two boundary points).
Figure 6: A point $p$ inside a polygon seeing several reflex vertices, illustrating the concept of Point Visibility Width.

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

Figure 4: The Iterated Comb construction used to prove that a chord can see exponentially more reflex vertices than a single point.

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

Abstract

Many problems in Discrete and Computational Geometry deal with simple polygons or polygonal regions. Many algorithms and data-structures perform considerably faster, if the underlying polygonal region has low local complexity. One obstacle to make this intuition rigorous, is the lack of a formal definition of local complexity. Here, we give two possible definitions and show how they are related in a combinatorial sense. We say that a polygon $P$ has point visibility width $w=pvw$, if there is no point $q\in P$ that sees more than $w$ reflex vertices. We say that a polygon $P$ has chord visibility width $w=cvw $, if there is no chord $c=\textrm{seg}(a,b)\subset P$ that sees more than w reflex vertices. We show that \[ cvw \leq pvw ^{O( pvw )},\] for any simple polygon. Furthermore, we show that there exists a simple polygon with \[ cvw \geq 2^{\Omega( pvw )}.\]
BibTeX
@misc{klute2021local,
  author = {Fabian Klute and Meghana M. Reddy and Tillmann Miltzow},
  title = {{Local Complexity of Polygons}},
  year = {2021},
  eprint = {2101.07554},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2101.07554},
}
Figure