Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2207.08708 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929319607009280 |
|---|---|
| author | Ripà, Marco |
| author_facet | Ripà, Marco |
| contents | Given any $n \in \mathbb{Z}^{+}$, we constructively prove the existence of covering paths and circuits in the plane which are characterized by the same link length of the minimum-link covering trails for the two-dimensional grid $G_n^2 := \{0,1, \ldots, n-1\} \times \{0, 1, \ldots, n-1\}$. Furthermore, we introduce a general algorithm that returns a covering cycle of analogous link length for any even value of $n$. Finally, we provide the tight upper bound $n^2 - 3 + 5 \cdot \sqrt{2}$ units for the minimum total distance travelled to visit all the nodes of $G_n^2$ with a minimum-link trail (i.e., a trail with $2 \cdot n - 2$ edges if $n$ is above two). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2207_08708 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Shortest polygonal chains covering each planar square grid Ripà, Marco Combinatorics 05C38 (Primary) 05C12, 91A43 (Secondary) Given any $n \in \mathbb{Z}^{+}$, we constructively prove the existence of covering paths and circuits in the plane which are characterized by the same link length of the minimum-link covering trails for the two-dimensional grid $G_n^2 := \{0,1, \ldots, n-1\} \times \{0, 1, \ldots, n-1\}$. Furthermore, we introduce a general algorithm that returns a covering cycle of analogous link length for any even value of $n$. Finally, we provide the tight upper bound $n^2 - 3 + 5 \cdot \sqrt{2}$ units for the minimum total distance travelled to visit all the nodes of $G_n^2$ with a minimum-link trail (i.e., a trail with $2 \cdot n - 2$ edges if $n$ is above two). |
| title | Shortest polygonal chains covering each planar square grid |
| topic | Combinatorics 05C38 (Primary) 05C12, 91A43 (Secondary) |
| url | https://arxiv.org/abs/2207.08708 |