1
$\begingroup$

Here is a key question (i.e., Question 2 below) that, if correctly answered, would let me support a very general conjecture on a wide class of related problems, a conjecture that I have never shared before.

In the Euclidean space $\ \mathbb{R}^3,\ $ let

$$ \mathcal H(4,3)\ :=\ \{0,1,2,3\}\times\{0,1,2,3\}\times\{0,1,2,3\} \,\ \subseteq\,\ \mathbb R^3 $$

We consider the family of all the distinct straight lines that joins at least two elements of $\mathcal{H}(4,3)$ (i.e., we need to take into account all the lines that pass through two distinct points among the $64$ given elements of the above mentioned cubic lattice).

Now, let us call $\mathcal{I_2}(4,3):=\{S_1,S_2, \dots, S_{t-1}\, S_t\}$ the set of all the (distinct) intesections of the family of lines above.

Question 1: Which is $t$, the cardinality of $\mathcal{I_2}(4,3)$?

Question 2: If we check by brute force all the possible polygonal chains consisting of $21$ or $22$ line segments (how many?), whose vertices always belong to $\mathcal{I_2}$, will we find at least one covering trail for $\mathcal{H}(4,3)$ (i.e., is it possible to draw at most $22$ consecutive links starting and ending on the vertices of $\mathcal{I_2}$ and joining in this way all the $64$ elements of the set $\mathcal{H}(4,3)$?)?

Current results: I have showed that we can constructively solve the problem by Question $2$ with a polygonal chain of length $23$ or less, Solution 4x4x4 with <span class=$23$ lines" /> whereas it is not possible to find any solution spending less than $21$ lines (trivial lower bound)1.

By improving my current upper bound, I would finally be able to strongly conjecture that the link length of any minimum-link covering trail for any set of $\{0,1,2,\dots,n-1\}\times\{0,1,2,\dots,n-1\} \times \dots \times\{0,1,2,\dots,n-1\}$ in $\mathbb{R}^k$ is equal to $\frac{n^k-1}{n-1}+n-3$ (here we are assuming that $n \in \mathbb{N}-\{0,1,2\}$ and $k \in \mathbb{N}-\{0,1\}$).
Otherwise, if we will be able to show that it is not possible to improve my upper bound of $23$ lines, I would infer that the general solution for the $\{0,1,2,\dots,n-1\}\times\{0,1,2,\dots,n-1\}\times \dots \times\{0,1,2,\dots,n-1\}\subset \mathbb{R}^k$ points problem is given by $\frac{n^k-1}{n-1}+(k-1)\cdot(n-3)$.

I am persuaded that the $22$ lines solution is likely to exist (or at least I strongly believe that it does not exist any covering trail consisting of only $21$ links that covers $\mathcal{H}(4,3)$), but I would not have many arguments to support my general claim without confirming the above by brute force testing.
Moreover, I have constructively proven that the link-length of the optimal covering trail for the set $\{0,1,2,3,4\}\times\{0,1,2,3,4\}\times\{0,1,2,3,4\} \subset \mathbb{R}^3$ belongs to $\{31, 32, 33, 34, 35, 36\}$, see the figure below enter image description here2.

Related OEIS sequence: A318165.

P.S. It is trivial to point out that all the $S_i$, for any $i=1,2,...,t$, necessarily belong to the Axis-Aligned Bounding Box $[-6,9] \times [-6,9] \times [-6,9]$.


Some useful References concerning the general problem:

1 - Proved untrivial bounds for the general problem) 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, 41(4):513–532, 2009.

2 - Proof that my general conjecture holds for $k=2$) B. Keszegh. Covering paths and trees for planar grids. Geombinatorics Quarterly, 24(1):5–10, 2014.

3 - General problem under some simplifying constraints) E. Kranakis, D. Krizanc, and L. Meertens. Link length of rectilinear Hamiltonian tours in grids. Ars Combinatoria, 38:177–192, 1994.

4 - Conjectures in conclusion) M. Ripà, Minimum-Link Covering Trails for any Hypercubic Lattice, arXiv, 2022.

5 - Proof that my general conjecture holds for $n=3$) M. Ripà. Solving the 106 years old 3k points problem with the clockwise-algorithm. Journal of Fundamental Mathematics and Applications, 3(2):84–97, 2020.

Announcement) We have also proven that it is possible to solve the general case ($n=2, k=k$) with exactly $3 \cdot 2^{k-2}$ lines and the full paper will be released in a couple of weeks.

$\endgroup$
10
  • 1
    $\begingroup$ Your title says something about the motivation for the problem, but almost nothing about the problem itself, so it might be a good idea to make it more informative. $\endgroup$
    – LSpice
    Oct 17, 2022 at 20:28
  • 1
    $\begingroup$ Thank you, References added. $\endgroup$ Oct 17, 2022 at 20:59
  • 1
    $\begingroup$ In the 2nd sentence, $k$ is meant to be $3$, right? $\endgroup$ Oct 18, 2022 at 5:00
  • 1
    $\begingroup$ This is a second request (following @LSpice) for a more informative title. $\endgroup$ Oct 18, 2022 at 22:55
  • 1
    $\begingroup$ I feel that the last phrase of the title, "in order to answer to a very general question", should be removed. $\endgroup$
    – Wlod AA
    Oct 19, 2022 at 2:42

1 Answer 1

6
$\begingroup$

In order to address Q1, I have computes all intersection points and all maximal line segments between such points (including all intermediate points). There are 13,307 intersection points and 1,492 maximal line segments, respectively. They are available at gist.

Just an example, the first listed maximal line segment composed of 20 points in order:

[(-2, -3, 7), (-1, -1, 5), (-1/2, 0, 4), (-1/3, 1/3, 11/3), (0, 1, 3), (1/4, 3/2, 5/2), (1/3, 5/3, 7/3), (2/5, 9/5, 11/5), (3/7, 13/7, 15/7), (1/2, 2, 2), (3/5, 11/5, 9/5), (2/3, 7/3, 5/3), (3/4, 5/2, 3/2), (4/5, 13/5, 7/5), (6/7, 19/7, 9/7), (1, 3, 1), (4/3, 11/3, 1/3), (3/2, 4, 0), (2, 5, -1), (3, 7, -3)]

$\endgroup$
7
  • 3
    $\begingroup$ Awesome work, Max. I'd like to cite your list in a future preprint discussing the conjecture on the general solution for any pair ($n,k$). Anyway, if somebody will find any solution with less than $23$ lines (i.e., $22$ links or $21$, maybe... even if I do not think that such a trail can exist), please let me know and I will be happy to add him/her as a coauthor of the next preprint or to add his/her published covering path as a reference, since this would be a great evidence supporting my final conjecture. $\endgroup$ Oct 18, 2022 at 22:12
  • $\begingroup$ No problem. I'm checking if the problem can be solved via ILP. Can you please share coordinates of endpoints of your 23 line segments? $\endgroup$ Oct 20, 2022 at 1:26
  • $\begingroup$ Of course. Here is the covering trail represented in my Figure, $(3,3,1)$-$(1,3,1)$-$(-2,0,1)$-$(4,0,1)$-$(3,0,3)$-$(3,3,3)$-$(0,0,0)$-$(3,0,0)$-$(0,3,3)$-$(0,0,3)$-$(3,3,0)$-$(-1,3,0)$-$(2,3,3)$-$(2,-1,3)$-$(-1,2,0)$-$(4,2,0)$-$(1,-1,3)$-$(1,4,3)$-$(4,1,0)$-$(-1,1,0)$-$(3,3,2)$-$(3,-2,2)$-$(0,7,2)$-$(0,0,2)$, but we can easily modify it as follows: $(3,3,1)$-$(1,3,1)$-$(-2,0,1)$-$(4,0,1)$-$(3,0,3)$-$(3,3,3)$-$(0,0,0)$-$(3,0,0)$-$(0,3,3)$-$(0,0,3)$-$(3,3,0)$-$(-1,3,0)$-$(2,3,3)$-$(2,-1,3)$-$(-1,2,0)$-$(4,2,0)$-$(1,-1,3)$-$(1,4,3)$-$(4,1,0)$-$(-1,1,0)$-$(3,3,2)$-$(3,0,2)$-$(0,3,2)$-$(0,0,2)$. $\endgroup$ Oct 20, 2022 at 17:58
  • $\begingroup$ If it helps, my covering trail with $36$ lines for the set $\mathcal{H}(5,3)$ is $(2,3,3)$-$(-1,0,3)$-$(4,0,3)$-$(0,4,3)$-$(5,4,3)$-$(3,2,1)$-$(-1,0,1)$-$(4,5,1)$-$(4,0,1)$-$(0,0,1)$-$(0,4,1)$-$(5,-1,1)$-$(3,3,3)$-$(0,-3,0)$-$(0,5,0)$-$(4,1,4)$-$(-1,1,4)$-$(3,5,0)$-$(3,0,0)$-$(-1,4,4)$-$(4,4,4)$-$(4,0,0)$-$(4,4,0)$-$(0,0,4)$-$(5,0,4)$-$(1,4,0)$-$(1,-1,0)$-$(5,3,4)$-$(0,3,4)$-$(2,-1,0)$-$(2,4,0)$-$(4,2,4)$-$(0,2,4)$-$(4,0,2)$-$(0,0,2)$-$(0,4,2)$-$(4,4,2)$. $\endgroup$ Oct 20, 2022 at 18:30
  • 1
    $\begingroup$ @EdoardoSerra: I've added my Sage code to the same gist. $\endgroup$ Nov 28, 2023 at 17:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.