Minimum number of edges for a tree that joins the $27$ nodes of a $3 \times 3 \times 3$ regular grid

76 Views Asked by At

In 2014, Dumitrescu and Tóth (see Covering Grids by Trees, Figure 2) proved the existence of an inside-the-box tree consisting of $13$ connected line segments covering all the $27$ nodes of the regular grid $G_{3}^3:=\{\{0,1,2\} \times \{0,1,2\} \times \{0,1,2\}\}$ in $\mathbb{R}^3$.

Now, in recent years, I showed that the mentioned configuration is not optimal as we remove the constraint to solve the problem inside the box (i.e., without letting any segment of the covering tree go outside the AABB $[0,2]\times[0,2]\times[0,2]$).
My constructive proof of the existence of a tree covering $G_{3}^3$ with no more than $12$ line segments is shown below.

enter image description here

Question: Is my solution optimal or we can do even better for the given problem?


Update: Following Joriki's request in the comments, let me properly describe the whole tree shown in the Figure.

RED: $\{\overline{(0,0,0)-(0,4,0)} \cup \overline{(0,4,0)-(2,0,2)}\}$.

BLUE: $\{\overline{(0,0,1)-(0,2,1)} \cup \overline{(0,1,1)-(2,1,1)} \cup \overline{(2,0,1)-(2,2,1)} \cup \overline{(2,1,0)-(2,1,2)}\}$.

GREEN: $\{\overline{(1,2,0)-(1,0,0)} \cup \overline{(1,0,0)-(2,2,2)}\}$.

PINK: $\{\overline{(1,0,2)-(1,2,2)} \cup \overline{(1,2,2)-(2,0,0)}\}$.

GOLD: $\{\overline{(0,2,2)-(0,-2,2)} \cup \overline{(0,-2,2)-(2,2,0)}\}$.

Then, there are three intersection points and they are located at:
[RED $\cap$ PINK] $=\left(\frac{4}{3},\frac{4}{3},\frac{4}{3} \right)$;
[GREEN $\cap$ BLUE $\cap$ PINK] $=\left(\frac{3}{2},1,1 \right)$;
[GREEN $\cap$ GOLD] $=\left(\frac{4}{3},\frac{2}{3},\frac{2}{3} \right)$.