Journal of Integer Sequences, Vol. 21 (2018), Article 18.9.8

Planar Additive Bases for Rectangles


Jukka Kohonen
Department of Computer Science
University of Helsinki
P.O. Box 68
FI-00014 University of Helsinki
Finland

Visa Koivunen and Robin Rajamäki
Department of Signal Processing and Acoustics
Aalto University
P.O. Box 15400
FI-00076 Aalto
Finland

Abstract:

We study a generalization of additive bases into a planar setting. A planar additive basis is a set of non-negative integer pairs whose vector sumset covers a given rectangle. Such bases find applications in active sensor arrays used in, for example, radar and medical imaging.

We propose two algorithms for finding the minimal bases of small rectangles: one in the unrestricted case where the basis elements can be anywhere in the rectangle, and another in the restricted case, where the elements are confined to the lower left quadrant. We present numerical results from such searches, including the minimal cardinalities and number of unique solutions for all rectangles up to [0, 11] × [0, 11] in the unrestricted case, and up to [0, 26] × [0, 26] in the restricted case. For squares we list the minimal basis cardinalities up to [0, 13] × [0, 13] in the unrestricted case, and up to [0, 46] × [0, 46] in the restricted case. Furthermore, we prove asymptotic upper and lower bounds on the minimal basis cardinality for large rectangles.


Full version:  pdf,    dvi,    ps,    latex    


(Concerned with sequences A001212 A008574 A295771 A295774.)


Received August 15 2018; revised version received December 17 2018. Published in Journal of Integer Sequences, December 17 2018.


Return to Journal of Integer Sequences home page