Improved Bounds for Covering Paths and Trees in the Plane

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 $\pi (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 $\pi (n)$ edges. Let $\tau (n)$ be the analogous number for noncrossing covering trees. Dumitrescu, Gerbner, Keszegh, and Tóth (Discrete & Computational Geometry, 2014) established the following inequalities: $$\frac{5n}{9}-O(1)<\pi (n)<(1-\frac{1}{601080391})n,\text{and}\frac{9n}{17}-O(1)<\tau (n)⩽\lfloor \frac{5n}{6}\rfloor \mathrm{.}$$ We report the following improved upper bounds: $$\pi (n)⩽(1-\frac{1}{22})n,\text{and}\tau (n)⩽\lceil \frac{4n}{5}\rceil \mathrm{.}$$ 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 $\rho (k)$ be the minimum number such that every $k$-colored point set in the plane admits a perfect rainbow polygon of size $\rho (k)$. Flores-Peñaloza, Kano, Martínez-Sandoval, Orden, Tejel, Tóth, Urrutia, and Vogtenhuber (Discrete Mathematics, 2021) proved that $20k\mathrm{/}19-O(1)<\rho (k)<10k\mathrm{/}7+O(1)\mathrm{.}$ We report the improved upper bound $\rho (k)<7k\mathrm{/}5+O(1)$. To obtain the improved bounds we present simple $O(n\log n)$-time algorithms that achieve paths, trees, and polygons with our desired number of edges.