skip to main content

GENERAL UNCROSSING COVERING PATHS INSIDE THE AXIS-ALIGNED BOUNDING BOX

*Marco Ripà  -  sPIqr Society, World Intelligence Network, Italy

Citation Format:
Abstract

Given the finite set of n_1⋅n_2⋅...⋅n_k points G(n_1,n_2,...,n_k) in R^𝑘 such that n_k...≥n_2n_1∈Z+, we introduce a new algorithm, called MΛI, which returns an uncrossing covering path inside the minimum axis-aligned bounding box [0,n_1−1]×[0,n_2−1]×...×[0,n_k−1], consisting of 3⋅(n_1⋅n_2⋅...⋅n_k−1)−2 links of prescribed length n_k−1 units. Thus, for any n_k≥3, the link length of the covering path provided by our MΛI-algorithm is smaller than the cardinality of the set G(n_1,n_2,...,n_k). Furthermore, assuming k>2, we present an uncrossing covering path for G(3,3,...,3), comprising only 20*3^(k−3)−2 two units long edges, which is constrained by the axis-aligned bounding box [0,4−√3]×[0,4−√3]×[0,2]×...×[0,2].

Fulltext View|Download
Keywords: Optimization; Link distance; Minimum bounding box; Covering path; MΛI-algorithm

Article Metrics:

  1. P. Eades and N.C. Wormald, “Fixed edge-length graph drawing is NP-Hard”, Discrete Applied Mathematics, vol. 28, pp. 111–134, 1990
  2. S. Bereg, P. Bose, A. Dumitrescu, F. Hurtado and P. Valtr, “Traversing a Set of Points with a Minimum Number of Turns”, Discrete & Computational Geometry, vol. 41, no. 4, pp. 513-532, 2009
  3. M. Ripà, “Reducing the clockwise-algorithm” to k length classes”, Journal of Fundamental Mathematics and Applications, vol. 4, no. 1, pp. 61–68, 2021
  4. S. Gravier and A. Parreau, “Hamiltonicité dans une grille, un jeu d’enfant ?”, Internal report, École Normale Supérieure de Lyon, 2006. http://enslyon.free.fr/rapports/info/Aline_Parreau_1.pdf
  5. M. Ripà, “Solving the n_1 ≤ n_2 ≤ n_3 Points Problem for n_3 < 6, ResearchGate, 25 Jun. 2020. https://www.researchgate.net/publication/342331014_Solving_the_n_1_n_2_n_3_Points_Problem_for_n_3_6
  6. E. Kranakis, D. Krizanc and L. Meertens, “Link length of rectilinear Hamiltonian tours in grids”, Ars Combinatoria, vol. 38, pp. 177–192, 1994
  7. D.P. Wagner, “Path planning algorithms under the link-distance metric”, Dartmouth College Ph.D. Dissertations, no. 16, 2006. https://digitalcommons.dartmouth.edu/dissertations/16/
  8. M. Hohenwarter, M. Borcherds, G. Ancsin, B. Bencze, M. Blossier, J. Elias, K. Frank, L. Gal, A. Hofstaetter, F. Jordan, B. Karacsony, Z. Konecny, Z. Kovacs, W. Kuellinger, E. Lettner, S. Lizelfelner, B. Parisse, C. Solyom-Gecse and M. Tomaschko, “GeoGebra - Dynamic Mathematics for Everyone - version 6.0.507.0-w”, International GeoGebra Institute, 16 Oct. 2018. https://www.geogebra.org
  9. M. Ripà, “Solving the 106 years old 3^k Points Problem with the clockwise-algorithm”, Journal of Fundamental Mathematics and Applications, vol. 3, no. 2, pp. 84–97,
  10. S. Loyd, “Cyclopedia of Puzzles”, The Lamb Publishing Company, New York, p. 301, 1914
  11. A. Dumitrescu and C. Tóth, “Covering Grids by Trees”, 26th Canadian Conference on Computational Geometry, 2014
  12. J. Tannery, “Manuscrits de Évariste Galois / publiés par Jules Tannery”, Gauthier-Villars, Paris, p. 27, 1908

Last update:

No citation recorded.

Last update:

No citation recorded.