2026-10-01T07:51:44Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26043 2026-09-23T23:58:35Z ddc:004 open_access

On the Doubling Dimension and the Perimeter of Geodesically Convex Sets in Fat Polygons de Berg, Mark Bose, Prosenjit Theocharous, Leonidas Fat polygons doubling dimension 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 (α,β)-covered polygon does have bounded doubling dimension (even if it has holes). We also study the perimeter of geodesically convex sets in (α,β)-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 (α,β)-covered polygons, including an algorithm that computes the closest pair of a set of m points in an (α,β)-covered polygon with n vertices that runs in O(n + mlog n) expected time. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mark de Berg and Prosenjit Bose and Leonidas Theocharous 2026 Is Part Of LIPIcs, Volume 370, 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SWAT.2026.7 urn:nbn:de:0030-drops-260439 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2026.7 eng https://creativecommons.org/licenses/by/4.0/legalcode