Nearly Optimal Robust Positioning Patterns.

A robust positioning pattern is a large array in which the contents of any subarray of given dimension can determine the subarray’s position, even if they are corrupted by errors. In this paper, we propose new explicit constructions and efficient locating algorithms for robust positioning patterns, which improve upon the previous results in two parameter regimes. For robustness against a constant fraction of errors, we construct the first infinite family of $q$ -ary robust positioning patterns whose rate asymptotically achieves the Singleton bound. For robustness against a constant number of errors, we present the first infinite family of binary robust positioning patterns where the gap between the redundancy and the lower bound is logarithmic in the subarray size and independent of the number of errors. Along with these explicit constructions, we also give efficient locating algorithms with time complexity quartic or cubic in the subarray size. [ABSTRACT FROM AUTHOR]