Improved Bounds for Covering Paths and Trees in the Plane

Abstract

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) < π(n) < \left(1-\frac{1}{601080391}\right)n, \quad\text{and} \quad\frac{9n}{17} - O(1) < τ(n)\leqslant \left\lfloor\frac{5n}{6}\right\rfloor.\] We report the following improved upper bounds: \[π(n)\leqslant \left(1-\frac{1}{22}\right)n, \quad\text{and}\quad τ(n)\leqslant \left\lceil\frac{4n}{5}\right\rceil.\] 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/19-O(1)<\rho (k)<10k/7+O(1).$ We report the improved upper bound $\rho (k)<7k/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.

17 pages, 6 figures, SoCG 2023