An Improved Bound for Plane Covering Paths

Abstract

A covering path for a finite set $P$ of points in the plane is a polygonal path such that every point of $P$ lies on a segment of the path. The vertices of the path need not be at points of $P$. A covering path is plane if its segments do not cross each other. Let $\ddot{I}€(n)$ be the minimum number such that every set of $n$ points in the plane admits a plane covering path with at most $\ddot{I}€(n)$ segments. We prove that $\ddot{I}€(n)\le \lceil 6n/7\rceil$. This improves the previous best-known upper bound of $\lceil 21n/22\rceil$, due to Biniaz (SoCG 2023). Our proof is constructive and yields a simple $O(n\log n)$-time algorithm for computing a plane covering path.

11 pages, 5 figures, ESA 2025