Covering Grids by Trees.
Adrian Dumitrescu, Csaba D. Tóth · 2014
Given n points in the plane, a covering tree is a tree whose edges are line segments that jointly cover all the points. Let Gdn be a n × · · · × n grid in Zd. It is known that G3n can be covered by an axis-aligned polygonal path with 32n 2 + O(n) edges, thus in particular by a polygonal tree with that many edges. Here we show that every covering tree for the n3 points of G3n has at least (1 + c3)n 2 edges, for some constant c3> 0. On the other hand, there exists a covering tree for the n3 points of G3n consisting of only n 2 +n+ 1 line segments, where each segment is either a single edge or a sequence of collinear edges. Extensions of these problems to higher dimensional grids (i.e., Gdn for d ≥ 3) are also examined. 1