An Improved Bound for Plane Covering Paths
By: Hugo A. Akitaya , Greg Aloupis , Ahmad Biniaz and more
Potential Business Impact:
Draws a line connecting dots without crossing.
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 $\pi(n)$ be the minimum number such that every set of $n$ points in the plane admits a plane covering path with at most $\pi(n)$ segments. We prove that $\pi(n)\le \lceil6n/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.
Similar Papers
A note on non-crossing path partitions in the plane
Computational Geometry
Counts ways to connect points without lines crossing.
Curves, points, incidences and covering
Combinatorics
Finds fewest lines to connect dots.
Bounding a Polygon by a Minimum Number of Vertices
Computational Geometry
Finds smallest box to hold any shape.