Abstract
A covering path for a planar point set is a path drawn in the plane with straightline 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) < (11/601080391)n, and 9n/17  O(1) < τ(n) ⩽ ⌊5n/6⌋. We report the following improved upper bounds: π(n) ⩽ (11/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 kcolored point set in the plane admits a perfect rainbow polygon of size ρ(k). FloresPeñaloza, Kano, MartínezSandoval, 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.
BibTeX  Entry
@InProceedings{biniaz:LIPIcs.SoCG.2023.19,
author = {Biniaz, Ahmad},
title = {{Improved Bounds for Covering Paths and Trees in the Plane}},
booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)},
pages = {19:119:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772730},
ISSN = {18688969},
year = {2023},
volume = {258},
editor = {Chambers, Erin W. and Gudmundsson, Joachim},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/17869},
URN = {urn:nbn:de:0030drops178696},
doi = {10.4230/LIPIcs.SoCG.2023.19},
annote = {Keywords: planar point sets, covering paths, covering trees, rainbow polygons}
}
Keywords: 

planar point sets, covering paths, covering trees, rainbow polygons 
Collection: 

39th International Symposium on Computational Geometry (SoCG 2023) 
Issue Date: 

2023 
Date of publication: 

09.06.2023 