General uncrossing covering paths inside the axis-aligned bounding box

Abstract

Given the finite set of $n_1\cdot n_2\cdot \dots \cdot n_k$ points $G_{n_1,n_2,\dots ,n_k}\subset {\mathbb{R}}^k$ such that $n_k\ge \cdots \ge n_2\ge n_1\in {\mathbb{Z}}^{+}$, we introduce a new algorithm, called M$\Lambda$I, which returns an uncrossing covering path inside the minimum axis-aligned bounding box $[0,n_1-1]\times [0,n_2-1]\times \cdots \times [0,n_k-1]$, consisting of $3\cdot {\prod }_{i=1}^{k-1}{n}_i-2$ links of prescribed length $n_k-1$ units. Thus, for any $n_k\ge 3$, the link length of the covering path provided by our M$\Lambda$I-algorithm is smaller than the cardinality of the set $G_{n_1,n_2,\dots ,n_k}$. Furthermore, assuming $k>2$, we present an uncrossing covering path for $G_{3,3,\dots ,3}$, consisting of $20\cdot 3^{k-3}-2$ straight-line edges that are $2$ units long each, which is constrained by the axis-aligned bounding box $\left[0,4-\sqrt{3}\right]\times \left[0,4-\sqrt{3}\right]\times [0,2{]}^{k-2}$.

14 pages, 9 figures

References in corpus (1)

• Solving the $106$ years old $3^k$ points problem with the clockwise-algorithm