New structural limits for empty pentagons and hexagons in point sets
Visibility Sets, Empty Pentagons, and Sufficient Conditions for Hexagons
Computational Geometry
Summary
This paper studies how certain groups of points in the plane can form empty shapes called pentagons and hexagons that contain no other points inside them. The authors define and analyze special subsets of points related to visibility from edges, called C-sets, and use these to better understand how many empty pentagons can occur. Their work leads to improved lower bounds on the number of empty pentagons in any large point set, although the insights for hexagons are less strong. The main contribution is the new way of structuring and bounding these visibility sets and how this relates to counting empty polygons.
What this means in practice
- •For computational geometry software developers: Improve geometric algorithms that count or detect empty convex polygons in 2D point sets using new bounds on visibility sets.
- •For computer graphics engineers: Enhance computations of visibility and extreme points for rendering or spatial analysis by utilizing structural properties of visibility-related point sets.
A theory result. No direct application yet.
Authors
Carlos M. Nicolas
Abstract
Given a set $S$ of $n$ points in general position in the plane, we define the $C$-set $C(p,q)$ of an oriented edge $(p,q)$ as the set of extreme points of the visibility set $V(p,q)$ facing $(p,q)$. Since every point of $V(p,q)$ that is not in $C(p,q)$ gives rise to an empty convex pentagon having $(p,q)$ as a boundary edge, it is natural to study the properties of $C$-sets in order to bound the number of empty convex pentagons of $S$. We prove tight bounds on the intersection size and union complexity of $C$-sets sharing an endpoint. We also consider the problem of bounding the number of empty pentagons and hexagons in terms of the number of interior and boundary points of $S$. While the hexagon bound is weak, it offers a potential step toward a superlinear lower bound. On the other hand, the two-parameter bound for pentagons, combined with the structural results on $C$-sets, yields a simple proof of an $Ω(n^{3/2})$ bound for the number of pentagons. While this is a significant improvement over previously published bounds, a recent preprint \cite{Astudillo2026} attains a better bound using completely different methods. Thus, the primary contribution of this paper lies in the structural results about $C$-sets and the two-parameter bounds for empty pentagons and hexagons.