

A319259


Minimal number of straight lines of a covering tree needed to cover n X n X n points arranged in a 3D 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 (ktimes n), every optimal covering tree has (exactly) 2^(k1) rectilinear segments, thus 2^(31) = 4 lines for the 2 x 2 x 2 case.
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

Table of n, a(n) for n=1..4.
A. Dumitrescu, C. D. Tóth, Covering Grids by Trees, 26th Canadian Conference on Computational Geometry, 2014.
M. Ripà, The rectangular spiral or the n1 X n2 X ... X nk Points Problem, Notes on Number Theory and Discrete Mathematics, 2014, 20(1), 5971.


FORMULA

a(n) = n^2 + n for even n.
a(n) = n^2 + n + 1 for odd n (conjectured).


EXAMPLE

For n = 3 the a(3) = 13 represents the minimum line segments to cover a 3 X 3 X 3 points (symmetrical) grid.


CROSSREFS

Cf. A058992, A225227, A261547, A318165.
Sequence in context: A141491 A292363 A119048 * A241264 A066993 A297884
Adjacent sequences: A319256 A319257 A319258 * A319260 A319261 A319262


KEYWORD

nonn,hard,more,bref


AUTHOR

Marco Ripà, Sep 15 2018


STATUS

approved



