CS Paper Radar

Visibility Sets, Empty Pentagons, and Sufficient Conditions for Hexagons

Carlos M. Nicolas

cs.CG math.CO ·submitted 2026-10-16 14:42 UTC · v1
theory

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.

Comment
21 pages, 12 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Curves of constant width and Lebesgue's covering problem

cs.CG math.MG ·2026-08-31 ·Ujjwal Mishra
theory similarity 0.70
Abstract

A universal cover is a convex set in the plane that contains a congruent copy of every planar set of diameter one. Lebesgue asked in 1914 for one of least area, and the value is not known. We prove that every convex universal cover has area at least 0.8344, improving on 0.832, published in 2005, and 0.833, in a 2026 preprint, both of which come from a disc together with an equilateral triangle and a regular pentagon. Our test sets are instead curves of constant width: the disc, the Reuleaux triangle and the Reuleaux pentagon. Each contains the regular polygon it is built on, so the family is strictly larger at the same number of bodies and the same number of placement parameters, and we show that the classical configuration admits an arrangement whose hull has area below 0.8336, so no bound drawn from those three sets by this argument reaches ours. Curves of constant width were proposed for this role, and explored numerically, by Gibbs in 2014; what is added here is a proof. It consists of an analytic reduction followed by one finite computation. The reduction bounds the hull area from below over an entire box of placements at once, by eroding each Reuleaux polygon to a fixed set contained in every placement that box allows. The computation is an exhaustive subdivision of the resulting five-dimensional space, recorded as a certificate of 486,799,600 nodes and checked by a verifier independent of the search, with a rigorous bound on its floating point error some thousands of times smaller than the margin the verification attains.

0.16

New Quantitative Bounds for the $(p,q)$-Theorem for Unions of Convex Sets

cs.CG math.CO ·2026-08-13 ·Chaya Keller, Shakhar Smorodinsky
theory similarity 0.65
Abstract · 21 pages

A set in $\mathbb{R}^d$ is $s$-convex if it is the union of at most $s$ convex sets. A family $F$ satisfies the $(p,q)$ property if among any $p$ sets in $F$, some $q$ intersect. Let $\mathrm{HD}_d^{(s)}(p,q)$ be the minimum number of points needed to pierce a finite family of $s$-convex sets that satisfies the $(p,q)$-property. Alon and Kalai (1995) proved that $\mathrm{HD}_d^{(s)}(p,q)$ exists for any $p \geq q \geq d+1$ and any $s \geq 1$, but the quantitative bounds they obtained are very loose. We present several improved upper and lower bounds, for a general $d$ and for $s$-intervals of the line (i.e., $\mathrm{HD}_1^{(s)}(p,q)$). In particular, we prove the following: (i) For every $d\ge2$, $s \geq 1$ and $δ>0$, if $p>q$ and $q\ge C_d\log(e sp)$, then $\mathrm{HD}_d^{(s)}(p,q) \le p-q+1 + O_{d,δ}((s \cdot \tfrac{p}{q} \cdot \log \tfrac{esp}{q})^{ρ_d+δ}),$ where $ρ_d<d$ is the exponent in the weak epsilon-net theorem of Rubin (2022). (ii) For $s \geq 1$, $p \geq q \geq 2$ and $q\ge C_0s\log(2s)\log(ep)$, $p-q+s \leq \mathrm{HD}_1^{(s)}(p,q) \leq p-q+2s+1$. This result provides the first near-tight estimate for $\mathrm{HD}_1^{(s)}(p,q)$ for $q>2$. (iii) For any fixed $s$, there are an integer $κ_s\in\{s,\ldots,2s\}$ and constants $C_s,p_s>0$ such that, whenever $p\ge p_s$ and $q\ge C_s\log(ep)$, $ \mathrm{HD}_1^{(s)}(p,q)\in\{p-q+κ_s,\;p-q+κ_s+1\}. $ Interestingly, this two-value concentration result holds, although the exact value of the threshold remains unknown. (iv) For any $s \geq 1$, $\mathrm{HD}_3^{(s)}(p,4) \geq sp^{2-o(1)}$. Already for families of convex sets, this significantly improves the best known lower bound on $\mathrm{HD}_d^{(1)}(p,d+1)$, for all $d \geq 3$.

0.38

Almost Empty Monochromatic Polygons in Planar Point Sets

cs.CG math.COcs.DM ·2026-10-05 ·Bhaswar B. Bhattacharya, Sandip Das, Sk Samim Islam, Aashirwad Mohapatra, Saumya Sen
publishedtheory similarity 0.64
Abstract · 28 pages, 9 figures

For integers $r \ge 3$, $c \ge 2$, and $s \ge 0$, let $\mathsf{M}_r^{\star}(c,s)$ denote the smallest integer such that any set of at least $\mathsf{M}_r^{\star}(c,s)$ points in the plane in general position (no three on a line), colored with $c$ colors, contains a monochromatic $r$-gon (not necessarily convex) with at most $s$ interior points. Define $λ_r^{\star}(c)$ to be the smallest integer such that $\mathsf{M}_r^{\star}(c,λ_r^{\star}(c)) < \infty$. The case of triangles, that is, $r=3$, has been studied in recent years. In this paper, we establish bounds on $λ_r^{\star}(c)$, for $r \ge 4$. Specifically, in the bichromatic case, we prove that $λ_r^{\star}(2)\leq \lfloor\frac{r-2}{2}\rfloor$, for every $r\geq3$. For hexagons, we sharpen this bound to $λ_6^{\star}(2)\leq1$, that is, every sufficiently large bichromatic planar point set in general position contains a monochromatic hexagon with at most one interior point. Next, for any number of colors $c\geq3$ and $r\geq3$, we show that $$(r - 2) \left \lfloor \frac{c-1}{2} \right \rfloor \leq λ_r^\star(c) \leq (r-2)(c-2)+\left\lfloor(r-2)δ_c\right\rfloor, $$ for some constant $δ_c \in (0, \frac{1}{2}]$, depending on $c$. The upper bounds combine spiral polygonizations with nested convex-hull arguments and, in the hexagon case, incidence counting in $4$-connected triangulations. The lower bounds follow from colored Horton-set constructions.

0.45

Containment Problems in Convex Sets

cs.CG cs.DMmath.CO ·2026-11-06 ·Prosenjit Bose, Bobby Miraftab, Tyler Tuttle
theory similarity 0.64
Abstract

Let $P$ be a set of $n$ points in the plane, and let $C$ be a compact, convex subset of the plane that contains the origin in its interior. We study the problem of finding two points $p$ and $q$ of $P$ with the property that any homothet of $C$ that contains $p$ and $q$ must contain at least a constant fraction of the points of $P$. We give proofs for several cases. When $C$ is strictly convex we achieve a fraction of $1/5$, and when $C$ is a general convex region we achieve a fraction of $1/6e$. We show how the ideas of this second bound can be used to prove a lower bound for a version of the problem in $\mathbb{R}^d$ when $C$ is a $d$-ball. We also consider a few special cases. When $C$ is a triangle we get a lower bound of $1/12$, and when we allow that triangle to be rotated by $π$ radians in addition to being scaled and translated we get a lower bound of $1/768$. In proving this last result, we improve the state of the art on the version of this problem in three dimensions, where $C$ is a parallelepiped. We also consider the algorithmic aspects of finding such a pair of points.

0.13

Triangle Covers of Polygons: Approximation Algorithms and Complexity

cs.CG ·2026-10-16 ·Linda Kleist, Lena Scherzer
similarity 0.61
Abstract · 37 pages, 32 figures, GeoGebra file

We study the geometric set cover problems of covering and partitioning a polygon into a minimum number of triangles. While the decision version of the covering problem is known to be APX-hard and $\exists\mathbb R$-complete (even for polygons without holes and vertices in general position), the computational complexity of partitioning a simple polygon into a minimum number of triangles is open. Our main result refutes a 40 year old conjecture by Asano, Asano, and Pinter stating that the triangle vertices of a minimum partition lie on intersection points of special lines, which are iteratively generated by the polygon vertices and the intersection points. In particular, we show that there exist polygons where all minimum triangle partitions need Steiner points with irrational coordinates. This indicates that the problem might be more complex than previously expected. Complementarily, we provide a simple constant factor approximation to compute a minimum triangle partition of a given polygon (possibly with holes). In the context of coverings, we devise the first constant factor approximation for computing a minimum triangle cover of a simple polygon. For general polygons, an $O(\log n)$-approximation follows by close inspection of previous work.

0.27

Computing the minimal perimeter polygon for digital objects in the triangular tiling

cs.CG ·2026-09-12 ·Petra Wiederhold
published similarity 0.61
Abstract · Preprint from November 11, 2024

This work presents an algorithm, together with its correctness proof, to determine the minimum perimeter polygon (MPP) for digital objects given as regular complexes in the triangular plane tiling. Such objects are edge-adjacency-connected sets of triangle tiles that have no end tiles, and the point set union of all their tiles forms a simple polygon. Nevertheless, the boundary paths of the objects are not assumed to be simple. Then the MPP is a weakly simple polygon that coincides with the relative convex hull (i.e., geodesic hull) of a set $A$ with respect to a simple polygon $B$, where $A\subset B$, but $A$ is not necessarily a polygon, in fact it is generally not connected. Our MPP algorithm relies on constructing and iteratively constraining cones of visibility through forthcoming boundary tiles, it uses the structure of the canonical boundary path, the MPP frontier is the shortest polygonal curve following this path. We also propose a boundary tracing algorithm to obtain such paths from the objects.

0.58

On the Spanning Ratio of the Greedy Triangulation for Convex Point Sets

cs.CG ·2026-08-10 ·Prosenjit Bose, Jean Lou de Carufel, Anil Maheshwari, Bobby Miraftab, Michiel Smid +1 more
theory similarity 0.60
Abstract

The greedy triangulation of a finite planar point set is obtained by considering all segments in nondecreasing order of length and inserting each segment that does not cross an earlier one. Its spanning ratio is known to be bounded by a universal constant, but the standard bound obtained from the diamond and good-polygon properties is about $11739.1$. We prove a substantially smaller bound for points in convex position. In particular, for every finite point set $P\subset\mathbb{R}^2$ in convex position and every pair $u,v\in P$, the greedy triangulation contains a $u$--$v$ path of length at most $κ|uv|$, where $κ<17.814$. Thus, the greedy triangulation of a convex point set is an $18$-spanner.

0.04

Every $k$-Quasi-Planar Graph Has Linearly Many Edges

cs.CG math.CO ·2026-11-01 ·Ankan Sadhu
theory similarity 0.60
Abstract · 6 pages, 1 figure

For every fixed integer $k\ge2$, we prove that every simple graph on $n$ vertices drawn in the plane with no $k$ pairwise crossing edges has at most $C_kn$ edges, where $C_k$ depends only on $k$. We allow any finite number of proper crossings between two edges, including edges with a common endpoint. For $n\ge3$, removing a small disk around each vertex turns the drawing into a family of arcs on a sphere with $n$ boundary circles. Each arc joins two different boundary circles, and different edges have different unordered pairs of endpoint circles. The arcs are therefore essential and pairwise nonhomotopic, with endpoints allowed to move along their boundary circles during a homotopy. Any family of pairwise intersecting lifts to the universal cover projects to distinct graph edges that cross pairwise. Its size is consequently at most $k-1$. Beeker and Lazarovich's theorem on surface patterns then bounds the number of arcs. Their estimate is linear in the size of a triangulation, and an explicit triangulation of the $n$-holed sphere has linearly many edges and triangles.

0.54