Shortest polygonal chains covering each planar square grid
Abstract
Given any n ∈ ℤ+, 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 Gn 2 := {0, 1, . . . , n − 1} × {0, 1, . . . , n −x 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 n2 − 3 + 5 · √2 units for the minimum total distance traveled to visit all the nodes of Gn 2 with a minimum-link trail (i.e., a trail with 2 · n − 2 edges if n is above two).
© 2026 Marco Ripà, published by Ludus Association
This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.