Robust positioning patterns with low redundancy
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...
| Main Authors: | , , , , |
|---|---|
| Other Authors: | |
| Format: | Journal Article |
| Language: | English |
| Published: |
2020
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/145046 |
| _version_ | 1811695826245779456 |
|---|---|
| author | Chee, Yeow Meng Dao, Duc Tu Kiah, Han Mao Ling, San Wei, Hengjia |
| author2 | School of Physical and Mathematical Sciences |
| author_facet | School of Physical and Mathematical Sciences Chee, Yeow Meng Dao, Duc Tu Kiah, Han Mao Ling, San Wei, Hengjia |
| author_sort | Chee, Yeow Meng |
| collection | NTU |
| description | 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. |
| first_indexed | 2024-10-01T07:29:38Z |
| format | Journal Article |
| id | ntu-10356/145046 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T07:29:38Z |
| publishDate | 2020 |
| record_format | dspace |
| spelling | ntu-10356/1450462023-02-28T19:27:19Z Robust positioning patterns with low redundancy Chee, Yeow Meng Dao, Duc Tu Kiah, Han Mao Ling, San Wei, Hengjia School of Physical and Mathematical Sciences Science::Mathematics Robust Positioning Patterns Gray Codes 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. Ministry of Education (MOE) Nanyang Technological University National University of Singapore (NUS), Temasek Laboratories Published version The research of the first, third, fourth, and fifth authors was supported in part bythe Singapore Ministry of Education under grant MOE2015-T2-2-086. The research of the fourthauthor was also supported in part by the Nanyang Technological University grant M4080456. 2020-12-09T06:18:21Z 2020-12-09T06:18:21Z 2020 Journal Article 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 0097-5397 https://hdl.handle.net/10356/145046 10.1137/19M1253472 2 49 284 317 en MOE2015-T2-2-086 M4080456 SIAM Journal on Computing © 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. application/pdf |
| spellingShingle | Science::Mathematics Robust Positioning Patterns Gray Codes Chee, Yeow Meng Dao, Duc Tu Kiah, Han Mao Ling, San Wei, Hengjia Robust positioning patterns with low redundancy |
| title | Robust positioning patterns with low redundancy |
| title_full | Robust positioning patterns with low redundancy |
| title_fullStr | Robust positioning patterns with low redundancy |
| title_full_unstemmed | Robust positioning patterns with low redundancy |
| title_short | Robust positioning patterns with low redundancy |
| title_sort | robust positioning patterns with low redundancy |
| topic | Science::Mathematics Robust Positioning Patterns Gray Codes |
| url | https://hdl.handle.net/10356/145046 |
| work_keys_str_mv | AT cheeyeowmeng robustpositioningpatternswithlowredundancy AT daoductu robustpositioningpatternswithlowredundancy AT kiahhanmao robustpositioningpatternswithlowredundancy AT lingsan robustpositioningpatternswithlowredundancy AT weihengjia robustpositioningpatternswithlowredundancy |