Improved Bounds for Covering Paths and Trees in the Plane
share
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 ρ(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.
READ FULL TEXT