arxiv: 2604.14471 · v2 · submitted 2026-04-15 · 💻 cs.CG

Recognition: unknown

On the Doubling Dimension and the Perimeter of Geodesically Convex Sets in Fat Polygons

Mark de Berg , Prosenjit Bose , Leonidas Theocharous

Authors on Pith no claims yet

Pith reviewed 2026-05-10 11:09 UTC · model grok-4.3

classification 💻 cs.CG

keywords doubling dimensionfat polygonsgeodesic distancegeodesically convex setsclosest pairpolygons with holescomputational geometry

0 comments

The pith

Fat polygons satisfying an (α,β)-covered condition have bounded doubling dimension under geodesic distance, even with holes.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that locally-fat simple polygons can fail to have bounded doubling dimension in the geodesic metric. Polygons meeting the stronger (α,β)-covered condition, however, always produce a metric space of bounded doubling dimension. The same condition also forces the perimeter of any geodesically convex set to stay within a constant factor of the set's Euclidean diameter. These two facts together let standard doubling-dimension techniques apply directly to the polygon, yielding an expected-time algorithm for closest pair that runs in O(n + m log n) for m points inside an n-vertex polygon.

Core claim

Any (α,β)-covered polygon has bounded doubling dimension with respect to geodesic distance, even when it contains holes. In addition, the perimeter of every geodesically convex set inside such a polygon is at most a constant times the Euclidean diameter of the set. These two properties together produce improved algorithms for several problems, including closest-pair computation in O(n + m log n) expected time.

What carries the argument

The (α,β)-covered fatness condition, which supplies enough local coverage to bound ball growth in the geodesic metric and to limit the length of geodesically convex boundaries.

Load-bearing premise

The polygon must satisfy the (α,β)-covered condition for fixed constants α and β.

What would settle it

An explicit (α,β)-covered polygon (with or without holes) in which some ball-doubling number grows without bound, or a geodesically convex set whose perimeter exceeds any fixed multiple of its Euclidean diameter.

Figures

Figures reproduced from arXiv: 2604.14471 by Leonidas Theocharous, Mark de Berg, Prosenjit Bose.

read the original abstract

Many algorithmic problems can be solved (almost) as efficiently in metric spaces of bounded doubling dimension as in Euclidean space. Unfortunately, the metric space defined by points in a simple polygon equipped with the geodesic distance does not necessarily have bounded doubling dimension. We therefore study the doubling dimension of fat polygons, for two well-known fatness definitions. We prove that locally-fat simple polygons do not always have bounded doubling dimension, while any $(\alpha,\beta)$-covered polygon does have bounded doubling dimension (even if it has holes). We also study the perimeter of geodesically convex sets in $(\alpha,\beta)$-covered polygons (possibly with holes), and show that this perimeter is at most a constant times the Euclidean diameter of the set. Using these two results, we obtain new results for several problems on $(\alpha,\beta)$-covered polygons, including an algorithm that computes the closest pair of a set of $m$ points in an $(\alpha,\beta)$-covered polygon with $n$ vertices that runs in $O(n + m\log{n})$ expected time.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper gives a clean counterexample showing locally-fat polygons can have unbounded doubling dimension, then proves that the stronger (α,β)-covered condition bounds it (even with holes) and yields an O(n + m log n) expected-time closest-pair algorithm.

read the letter

The core contribution is the separation between the two fatness notions and the resulting algorithmic payoff. The explicit construction for locally-fat polygons with increasingly narrow spikes makes the unbounded doubling dimension concrete and easy to verify. The positive result for (α,β)-covered polygons proceeds by showing geodesic balls can be covered by a constant number of smaller balls using the covering disks from the fatness definition, with a case analysis that handles boundary crossings and holes without extra factors. That bound is new for this definition. The perimeter claim for geodesically convex sets follows from splitting the boundary into a constant number of chains whose lengths are controlled by the Euclidean diameter via the same covering disks; this step looks tight and directly feeds the closest-pair result. The algorithm itself is a standard doubling-dimension net plus linear-time polygon preprocessing that gives an implicit geodesic oracle, so the O(n) term absorbs the setup cost and leaves the expected O(m log m) query work. No circularity or hidden parameters appear in the derivations. The main soft spot is that the doubling-dimension constant is left as some function of α and β without an explicit expression, which is common but means implementers will have to chase the proof for concrete numbers. The expected-time bound also assumes standard random sampling for the net, which is fine but not deterministic. This work is aimed at computational geometers who care about metric properties of polygonal domains. It is worth sending to peer review because the counterexample is solid, the proofs hold up on inspection, and the algorithmic consequence is a clear improvement over prior geodesic closest-pair bounds.

Referee Report

0 major / 3 minor

Summary. The paper claims that locally-fat simple polygons do not always have bounded doubling dimension under the geodesic metric, while any (α,β)-covered polygon (even with holes) does have doubling dimension bounded by a function of α and β. It further shows that the geodesic perimeter of any geodesically convex set in an (α,β)-covered polygon is at most a constant times the Euclidean diameter of the set. These two results are combined to obtain an algorithm computing the closest pair of m points in an n-vertex (α,β)-covered polygon in O(n + m log n) expected time.

Significance. If the results hold, the work is significant for computational geometry: it sharply delineates fatness conditions that yield bounded doubling dimension (enabling transfer of Euclidean-style algorithms) from those that do not, via an explicit counterexample construction with increasingly narrow features for the negative result. The positive doubling-dimension proof relies on geodesic-ball coverings from the (α,β) property plus case analysis on boundary interactions; the perimeter bound is obtained by decomposing the boundary into O(1) chains whose lengths are controlled by the covering disks and the Euclidean diameter. These enable a standard doubling-dimension net construction for closest pair together with linear-time polygon preprocessing that yields an implicit distance oracle whose cost is absorbed into the O(n) term. The explicit counterexample, case analysis, and reproducible algorithmic reduction are strengths.

minor comments (3)

[Abstract] Abstract: the statement that the perimeter is 'at most a constant times' the Euclidean diameter should indicate the dependence of the constant on α and β (even if only asymptotically), to make the quantitative claim fully precise.
[Proof of bounded doubling dimension] The case analysis establishing the doubling-dimension bound for (α,β)-covered polygons (with and without holes) would benefit from an explicit enumeration or diagram summarizing the boundary-interaction cases, to aid verification of completeness.
[Algorithmic application] In the closest-pair algorithm section, the claim that the implicit distance oracle cost is absorbed into the O(n) preprocessing term should cite the specific linear-time preprocessing subroutine (e.g., triangulation or visibility graph construction) used to support the oracle.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive review, accurate summary of our contributions, and recommendation for minor revision. We appreciate the assessment of the work's significance in computational geometry.

Circularity Check

0 steps flagged

No significant circularity in derivation chain

full rationale

The paper's results on doubling dimension for (α,β)-covered polygons and perimeter bounds for geodesically convex sets follow from explicit geometric arguments: a direct construction exhibiting unbounded dimension in locally-fat polygons, and a covering-property case analysis plus O(1)-chain decomposition for the (α,β) case. These feed into a standard doubling-net closest-pair algorithm whose O(n + m log n) bound absorbs preprocessing into linear time. No equations, definitions, or self-citations reduce any claimed bound to a fitted parameter or prior result by construction; the derivation is self-contained against the fixed fatness constants.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper relies on standard geometric axioms and existing fatness definitions without introducing new free parameters or postulated entities.

axioms (2)

standard math Geodesic distance inside a polygon forms a metric space
Used throughout the doubling-dimension analysis.
domain assumption The two fatness notions (locally-fat and (α,β)-covered) are well-defined as in prior literature
Central to classifying which polygons have bounded doubling dimension.

pith-pipeline@v0.9.0 · 5490 in / 1405 out tokens · 38113 ms · 2026-05-10T11:09:22.591490+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

5 extracted references · 5 canonical work pages

[1]

Agarwal, Matthew J

1 Pankaj K. Agarwal, Matthew J. Katz, and Micha Sharir. Computing depth orders for fat objects and related problems.Comput. Geom., 5:187–206, 1995.doi:10.1016/0925-7721(95) 00005-8. 2 Greg Aloupis, Prosenjit Bose, Vida Dujmovic, Chris Gray, Stefan Langerman, and Bettina Speckmann. Triangulating and guarding realistic polygons.Comput. Geom., 47(2):296–306,...

work page doi:10.1016/0925-7721(95 1995
[2]

XX:16 OntheDoublingDimensionandthePerimeterofGeodesicallyConvexSetsinFatPolygons 4 Glencora Borradaile, Hung Le, and Christian Wulff-Nilsen

doi: 10.1137/120891241. XX:16 OntheDoublingDimensionandthePerimeterofGeodesicallyConvexSetsinFatPolygons 4 Glencora Borradaile, Hung Le, and Christian Wulff-Nilsen. Greedy spanners are optimal in doubling metrics. InProceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2371–2379, 2019.doi:10.1137/1.9781611975482.145. 5 Pro...

work page doi:10.1137/120891241 2019
[3]

15 Alon Efrat

URL: https://www.sciencedirect.com/science/article/pii/S0196677497908737, doi:10.1006/jagm.1997.0873. 15 Alon Efrat. The complexity of the union of (alpha, beta)-covered objects.SIAM J. Comput., 34(4):775–787, 2005.doi:10.1137/S0097539702407515. 16 Alon Efrat, Matthew J. Katz, Frank Nielsen, and Micha Sharir. Dynamic data structures for fat objects and th...

work page doi:10.1006/jagm.1997.0873 1997
[4]

23 Mark H

doi:10.1137/ S009753979018330X. 23 Mark H. Overmars and A. Frank van der Stappen. Range searching and point location among fat objects.J. Algorithms, 21(3):629–656, 1996.doi:10.1006/JAGM.1996.0063. M. de Berg and P. Bose and L. Theocharous XX:17 24 Godfried Toussaint. An optimal algorithm for computing the relative convex hull of a set of points in a poly...

work page doi:10.1006/jagm.1996.0063 1996
[5]

doi:10.1016/0925-7721(93)90007-S. 27 A. Frank van der Stappen, Mark H. Overmars, Mark de Berg, and Jules Vleugels. Motion planning in environments with low obstacle density.Discret. Comput. Geom., 20(4):561–587, 1998.doi:10.1007/PL00009402. 28 J. Vleugels.On Fatness and Fitness—Realistic Input Models for Geometric Algorithms. PhD thesis, University Utrecht, 1997

work page doi:10.1016/0925-7721(93)90007-s 1998