login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

%I

%S 1,4,13,20

%N Minimal number of straight lines of a covering tree needed to cover n X n X n points arranged in a 3-D grid.

%C 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.

%C 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.

%C 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, ...

%H A. Dumitrescu, C. D. Tóth, <a href="https://www.semanticscholar.org/paper/Covering-Grids-by-Trees-Dumitrescu-T%C3%B3th/62989bdc3351ef8a8146b4e26b6c20b920a98ab2">Covering Grids by Trees</a>, 26th Canadian Conference on Computational Geometry, 2014.

%H M. Ripà, <a href="http://nntdm.net/volume-20-2014/number-1/59-71/">The rectangular spiral or the n1 X n2 X ... X nk Points Problem</a>, Notes on Number Theory and Discrete Mathematics, 2014, 20(1), 59-71.

%F a(n) = n^2 + n for even n.

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

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

%Y Cf. A058992, A225227, A261547, A318165.

%K nonn,hard,more,bref

%O 1,2

%A _Marco Ripà_, Sep 15 2018

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 19 04:40 EDT 2019. Contains 328211 sequences. (Running on oeis4.)