Please use this identifier to cite or link to this item:
Title: Robust positioning patterns with low redundancy
Authors: Chee, Yeow Meng
Dao, Duc Tu
Kiah, Han Mao
Ling, San
Wei, Hengjia
Keywords: Science::Mathematics
Issue Date: 2020
Source: Chee, Y. M., Dao, D. T., Kiah, H. M., Ling, S., & Wei, H. (2020). Robust positioning patterns with low redundancy. SIAM Journal on Computing, 49(2), 284-317. doi:10.1137/19M1253472
Project: MOE2015-T2-2-086 
Journal: SIAM Journal on Computing 
Abstract: A robust positioning pattern is a large array that allows a mobile device to locate its position by reading a possibly corrupted small window around it. In this paper, we provide constructions of binary positioning patterns, equipped with efficient locating algorithms, that are robust to a constant number of errors and have redundancy within a constant factor of optimality. Furthermore, we modify our constructions to correct rank errors and obtain binary positioning patterns robust to any errors of rank less than a constant number. Additionally, we construct $q$-ary robust positioning sequences robust to a large number of errors, some of which have length attaining the upper bound. Our construction of binary positioning sequences that are robust to a constant number of errors has the least known redundancy among those explicit constructions with efficient locating algorithms. On the other hand, for binary robust positioning arrays, our construction is the first explicit construction whose redundancy is within a constant factor of optimality. The locating algorithms accompanying both constructions run in time cubic in sequence length or array dimension.
ISSN: 0097-5397
DOI: 10.1137/19M1253472
Rights: © 2020 Society for Industrial and Applied Mathematics. All rights reserved. This paper was published in SIAM Journal on Computing and is made available with permission of Society for Industrial and Applied Mathematics.
Fulltext Permission: open
Fulltext Availability: With Fulltext
Appears in Collections:SPMS Journal Articles

Files in This Item:
File Description SizeFormat 
19m1253472.pdf837.58 kBAdobe PDFView/Open

Page view(s)

Updated on Jan 20, 2022


Updated on Jan 20, 2022

Google ScholarTM




Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.