2026-07-22T14:20:23Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17869 2024-03-06T11:00:34Z ddc:004 open_access

Improved Bounds for Covering Paths and Trees in the Plane Biniaz, Ahmad planar point sets covering paths covering trees rainbow polygons A covering path for a planar point set is a path drawn in the plane with straight-line edges such that every point lies at a vertex or on an edge of the path. A covering tree is defined analogously. Let π(n) be the minimum number such that every set of n points in the plane can be covered by a noncrossing path with at most π(n) edges. Let τ(n) be the analogous number for noncrossing covering trees. Dumitrescu, Gerbner, Keszegh, and Tóth (Discrete & Computational Geometry, 2014) established the following inequalities: 5n/9 - O(1) < π(n) < (1-1/601080391)n, and 9n/17 - O(1) < τ(n) ⩽ ⌊5n/6⌋. We report the following improved upper bounds: π(n) ⩽ (1-1/22)n, and τ(n) ⩽ ⌈4n/5⌉. In the same context we study rainbow polygons. For a set of colored points in the plane, a perfect rainbow polygon is a simple polygon that contains exactly one point of each color in its interior or on its boundary. Let ρ(k) be the minimum number such that every k-colored point set in the plane admits a perfect rainbow polygon of size ρ(k). Flores-Peñaloza, Kano, Martínez-Sandoval, Orden, Tejel, Tóth, Urrutia, and Vogtenhuber (Discrete Mathematics, 2021) proved that 20k/19 - O(1) < ρ(k) < 10k/7 + O(1). We report the improved upper bound of ρ(k) < 7k/5 + O(1). To obtain the improved bounds we present simple O(nlog n)-time algorithms that achieve paths, trees, and polygons with our desired number of edges. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ahmad Biniaz 2023 Is Part Of LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2023.19 urn:nbn:de:0030-drops-178696 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.19 eng https://creativecommons.org/licenses/by/4.0/legalcode