cp's OEIS Frontend

A generalization of the well-known "Nine Dots Problem", where the regular axis-aligned bounding box (RAABB:=[0, n] X [0, n] X [0, n]) has been declared.

From Marco Ripà, Aug 10 2020: (Start)

In particular, if we loosen the constraint on the allowed AABB, covering paths characterized by a shorter link-length can be found, such as 5 <= a(2) <= 6, where the aforementioned upper bound has been discovered by Koki Goma in August 2021, providing the self-crossing covering path (0,0,0)-(2,2,0)-(1/2,1/2,3/2)-(2,-1,0)-(0,1,0)-(0,1,1)-(0,0,1).

Moreover, the above pattern suggests different uncrossing covering paths of the same link-length, such as (1,0,0)-(0,0,0)-(2,2,2)-(1/2,-1,1/2)-(-1/2,1,3/2)-(1,1,0)-(1,1,0) and also the (self-crossing) covering path (1,0,0)-(0,0,0)-(0,1,0)-(3/2,1,3/2)-(1/2,-1,1/2)-(-1/2,1,3/2)-(1,1,0) which is entirely contained inside a box of 1.5 X 2 X 2 units^3 but which does not match the RAABB. (End)

The most natural mathematical generalization of the well-known "Nine Dots Problem" by Sam Loyd (published in Cyclopedia of puzzles, p. 301, in 1914) is an NP-hard challenge with no AABB, no constraint about visiting any vertex more than once or self-crossing lines, no restriction on the turning angles available.

This problem has been solved for n < 4 (see links), while it has been proved that a(4) is 21, 22, or 23, since a covering trail (for the n = 4 case) having 23 links is given by (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).

A covering trail for the n = 5 case with a link-length of 36 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).

It has been proved that it is not possible to join the 8 vertices of a cube with a polygonal chain that has fewer than 6 edges (see Links, Optimal cycles enclosing all the nodes of a k-dimensional hypercube, Theorem 2.2).

Here we consider the additional constraint of minimizing the total (Euclidean) length of the minimum-link polygonal chains (which consist of exactly 6 line segments connected at their endpoints) that join all the vertices of the cube [0,1] X [0,1] X [0,1].

A solution to the above-stated problem is provided by the 6-link polygonal chain (0,0,1)-(0,0,0)-(1+(x+2+sqrt(2))/(2*sqrt(2)(x+sqrt(2))),1+(x+2+sqrt(2))/(2*sqrt(2)(x+sqrt(2))),0)-(1/2,1/2,1+x/sqrt(2))-(- (x+2+sqrt(2))/(2*sqrt(2)(x+sqrt(2))),1+(x+2+sqrt(2))/(2*sqrt(2)(x+sqrt(2))),0)-(1,0,0)-(1,0,1), where x = (1/2)*sqrt((2/3)^(2/3)*((9+sqrt(177)))^(1/3) - 4*(2/(27+3*sqrt(177)))^(1/3)) + (1/2)*sqrt(4*(2/(27+3*sqrt(177)))^(1/3) - (2/3)^(2/3)*(9+sqrt(177))^(1/3) + 4*sqrt(2/((2/3)^(2/3)*(9+sqrt(177))^(1/3) - 4*(2/(27+3*sqrt(177)))^(1/3)))) = 1.597920933550032074764705350780465558827883608091828573735862154752648...

The total (Euclidean) length of the mentioned polygonal chain is about 11.105251123 and this value cannot be beaten by any other 6-link polygonal chain covering all the vertices belonging to the set {0,1} X {0,1} X {0,1} (a nice proof was posted on MathOverflow on June 5, 2024 by a new user, DR.LL, whose profile was subsequently deleted for unknown reasons).

A generalization of the well-known "Nine Dots Problem".

For any n > 3, an upper bound for this problem is given by U(n) := (t + 1)*n^(n - 3) - 1, where "t" is the best known solution for the corresponding n X n X n case, and (for any n > 5) t = floor((3/2)*n^2) - floor((n - 1)/4) + floor((n + 1)/4) - floor((n - 2)/4) + floor(n/2) + n - 2 (e.g., U(4) = 95, since 23 is the current upper bound for the 4 X 4 X 4 problem). In particular, it is easily possible to prove the existence of an Hamiltonian path without self crossing such that U(4) = 95 (in fact, an Hamiltonian path with link-length 23 for the 4 X 4 X 4 problem was explicitly shown in June 2020).

A (trivial) lower bound is given by B(n):= (n^n - 1)/(n - 1). - Marco Ripà, Aug 25 2020

It has been proved that it is not possible to join the 8 vertices of a cube with a polygonal chain that has fewer than 6 edges (see Links, Optimal cycles enclosing all the nodes of a k-dimensional hypercube, Theorem 2.2).

Here we are considering the additional constraint that asks to minimize the volume of the Axis-Aligned Bounding Box (AABB) including the above-mentioned optimal polygonal chain consisting of only 6 connected line segments and that joins all the vertices of the cube [0,1] X [0,1] X [0,1].

Given phi = (1+sqrt(5))/2, the well-known golden ratio (see A001622), a valid polygonal chain is (0, 1, 0)-(0, 0, 0)-((1+phi)/2, 0, (1+phi)/2)-(1/2, 1+phi, 1/2)-((1-phi)/2, 0, (1+phi)/2)-(1, 0, 0)-(1, 1, 0) (see Links, p. 164), and consequently the minimum volume AABB is [(1-phi)/2, (1+phi)/2] X [0, 1+phi] X [0, (1+phi)/2].

As noted by Hugo Pfoertner, the present sequence is also given by phi^5/2 (i.e., A244593/2).

The author conjectures that this is the minimum volume of an axis-aligned bounding box which includes the shortest minimum-link circuit joining all the vertices of the cube {0,1}^3 (i.e., the closed polygonal chains consisting of exactly 6 edges visiting all the points of the set {(0,0,0),(0,0,1),(0,1,0),(0,1,1),(1,0,0),(1,0,1),(1,1,0),(1,1,1)}).

In detail, such a circuit of 6 links is given by (1/2,1+phi,1/2)-((1-phi)/2,0,(1+phi)/2)-((phi+1)/2,0, (1-phi)/2)-(1/2,1+phi,1/2)-((phi+1)/2,0,(phi+1)/2)-((1-phi)/2,0,(1-phi)/2(1/2,1+phi,1/2), where phi := (1+sqrt(5))/2 (see A001622).

Then, phi*(2*phi + 1) = phi^2*(phi + 1) since phi - 1 = 1/phi.

It has been proved that it is not possible to join the 8 vertices of a cube with a polygonal chain that has fewer than 6 edges (see Links, Optimal cycles enclosing all the nodes of a k-dimensional hypercube, Theorem 2.2). Thus, any circuit of 6 line segments covering all the vertices of a cube has the minimum link-length (by definition).

Here we consider the additional constraint of minimizing the total (Euclidean) length of the minimum-link circuit (which consists of exactly 6 line segments connected at their endpoints) that joins all the vertices of the cube [0,1] X [0,1] X [0,1].

Let x := (1/2)*sqrt((2/3)^(2/3)*((9+sqrt(177)))^(1/3) - 4*(2/(27+3*sqrt(177)))^(1/3)) + (1/2)*sqrt(4*(2/(27+3*sqrt(177)))^(1/3) - (2/3)^(2/3)*(9+sqrt(177))^(1/3) + 4*sqrt(2/((2/3)^(2/3)*(9+sqrt(177))^(1/3) - 4*(2/(27+3*sqrt(177)))^(1/3)))) = 1.597920933550032074764705350780465558827883608091828573735862154752648..., and then let c := 1+(x+2+sqrt(2))/(2*sqrt(2)*(x+sqrt(2))).

A solution to the above-stated problem is provided by the 6-link circuit (1/2, 1/2, 1+x/sqrt(2))-(c,c,0)-(-c,-c,0)-(1/2,1/2, 1+x/sqrt(2))-(-c,c,0)-(c,-c,0)-(1/2, 1/2, 1+x/sqrt(2)).

The total (Euclidean) length of the mentioned circuit is given by 4*((2+sqrt(2)*x)/2)*(1/x+sqrt(1+1/x^2)) = which is about 11.105251123 and this value cannot be beaten by any other 6-link circuit covering all the vertices belonging to the set {0,1} X {0,1} X {0,1}. This result follows by symmetry from the optimal polygonal chain described in the comments of A373537.

For any n > 2, is it possible to construct an "inside the box" covering tree for any n X n X n set of points consisting of n^2 + n lines if n is even and n^2 + n + 1 lines if n is odd.

In the special case of any 2 X 2 X ... X 2 points problem (k-times n), every optimal covering tree has (exactly) 2^(k-1) rectilinear segments, thus 2^(3-1) = 4 lines for the 2 x 2 x 2 case.

If n = 3, then the (outside the box) solution is a(3) = 12, since such a connected arrangement of line segments has already been shown to exist, and this explicit upper bound matches 3^3 + 3. - Marco Ripà, Aug 25 2020

Let n >= 5, we know that it is impossible to cover more than n^3 points with n^2 segments (trivial), and we need at least n segments to obtain a connected graph (otherwise, we cannot join more than n + h*(n - 1) points with h + 1 connected lines). Thus, assuming n > 2, the general lower bound is confirmed to be n^2 + n, therefore a(n even) = 4, 20, 42, 72, ...