Multidimensional grid

The Rectangular Spiral or the n_1 × n_2 × · · · × n_k Points Problem

  • Marco Ripà
    • Categories Bound-constrained Optimization, Combinatorial Optimization, Graphs and Matroids Tags , , , , , , ,

    A generalization of Ripà’s square spiral solution for the n × n × ··· × n Points Upper Bound Problem. Additionally, we provide a non-trivial lower bound for the k-dimensional n_1 × n_2 × ··· × n_k Points Problem. In this way, we can build a range in which, with certainty, all the best possible … Read more

    Minimum-Link Covering Trails for any Hypercubic Lattice

  • Marco Ripà
    • Categories Combinatorial Optimization, Graphs and Matroids Tags , , , , ,

    In 1994, Kranakis et al. published a conjecture about the minimum link-length of every rectilinear covering path for the \(k\)-dimensional grid \(P(n,k) := \{0,1, \dots, n-1\} \times \{0,1, \dots, n-1\} \times \cdots \times \{0,1, \dots, n-1\}\). In this paper we consider the general, NP-complete, Line-Cover problem, where the edges are not required to be axis-parallel, … Read more