cp's OEIS Frontend

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.

This sequence describes the optimal solution of the 2D generalization of the well-known nine dots problem, published in Loyd’s Cyclopedia of Puzzles (1914), p. 301.

Since Solomon Golomb constructively proved that, for any n >= 3, the minimum-link polygonal chain covering a given {0,1,...,n-1} X {0,1,...,n-1} grid consists of (exactly) 2*(n - 1) line segments, we only need to find the shortest trail satisfying the constraint above.

In detail, if n = 2, the trivial spanning path (0,1)-(0,0)-(1,0)-(1,1) is optimal. If n = 3, we have the classic solution of the nine dots problem (0,1)-(0,3)-(3,0)-(0,0)-(2,2). Now, if n > 3, a valid upper bound is given by n^2 + 5*sqrt(2) - 3, but it is possible to improve this solution for the n = 5 case by providing the trail.

(2,3)-(4,3)-(1,0)-(1,3)-(4,0)-(0,0)-(0,4)-(4,4)-(4,1), whose total Euclidean length is 20 + 6*sqrt(2). In the end, assuming n > 5, we can recycle the mentioned solution, then extend the last line segment to reach (4,-1), and finally apply the square spiral pattern to the (extended) ending segment of the {0,1,...,n-1} X {0,1,...,n-1} grid solution in order to get the solution for the {0,1,...,n} X {0,1,...,n} case, joining 2*n + 1 more points by spending two additional line segments having a combined length of 2*n (and this is an iterative strategy which is optimal for any n > 5).