|
| |
|
|
A319259
|
|
Minimal number of straight lines of a covering tree needed to cover n X n X n points arranged in a 3-D grid.
|
|
0
|
| |
|
|
|
OFFSET
|
1,2
|
|
|
COMMENTS
|
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, ...
|
|
|
LINKS
|
|
|
|
FORMULA
|
a(n) = n^2 + n for even n and for n = 3. - Marco Ripà, Aug 25 2020
|
|
|
EXAMPLE
|
For n = 3 the a(3) = 12 represents the minimum line segments to cover a 3 X 3 X 3 points (symmetrical) grid. - Marco Ripà, Aug 25 2020
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,hard,more,bref
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
