An Improved Bound for Plane Covering Paths
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912472837914624 |
|---|---|
| author | Akitaya, Hugo A. Aloupis, Greg Biniaz, Ahmad Bose, Prosenjit De Carufel, Jean-Lou Gavoille, Cyril Iacono, John Kleist, Linda Smid, Michiel Souvaine, Diane Theocharous, Leonidas |
| author_facet | Akitaya, Hugo A. Aloupis, Greg Biniaz, Ahmad Bose, Prosenjit De Carufel, Jean-Lou Gavoille, Cyril Iacono, John Kleist, Linda Smid, Michiel Souvaine, Diane Theocharous, Leonidas |
| contents | 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 $π(n)$ be the minimum number such that every set of $n$ points in the plane admits a plane covering path with at most $π(n)$ segments. We prove that $π(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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_06477 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | An Improved Bound for Plane Covering Paths Akitaya, Hugo A. Aloupis, Greg Biniaz, Ahmad Bose, Prosenjit De Carufel, Jean-Lou Gavoille, Cyril Iacono, John Kleist, Linda Smid, Michiel Souvaine, Diane Theocharous, Leonidas Computational Geometry 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 $π(n)$ be the minimum number such that every set of $n$ points in the plane admits a plane covering path with at most $π(n)$ segments. We prove that $π(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. |
| title | An Improved Bound for Plane Covering Paths |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2507.06477 |