An Improved Bound for Plane Covering Paths
Hugo A. Akitaya, Greg Aloupis, Ahmad Biniaz, Prosenjit Bose, Jean-Lou De Carufel, Cyril Gavoille, John Iacono, Linda Kleist, Michiel Smid, Diane Souvaine, Leonidas Theocharous · 2025
Read An Improved Bound for Plane Covering Paths by Hugo A. Akitaya, Greg Aloupis, Ahmad Biniaz, Prosenjit Bose, Jean-Lou De Carufel, Cyril Gavoille, John Iacono, Linda Kleist, Michiel Smid, Diane Souvaine, Leonidas Theocharous (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-06477.txt.
Description
Hugo Akitaya and a large team improve the bound on how many segments a non crossing path needs to visit every point in a set, in work from 2025. A covering path runs through all points, but its turning points need not sit on them. The path must not cross itself, which makes short routes harder to find.
The team proves that a number of segments equal to about six sevenths of the point count always suffices. That beats the best prior bound by a clear margin. Their proof is constructive: it gives a fast algorithm that builds such a path for any point set. The result sharpens a classic geometry question.
Catalog record
| CREATOR | Hugo A. Akitaya, Greg Aloupis, Ahmad Biniaz, Prosenjit Bose, Jean-Lou De Carufel, Cyril Gavoille, John Iacono, Linda Kleist, Michiel Smid, Diane Souvaine, Leonidas Theocharous |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 23 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-06477