Robust positioning patterns with low redundancy

DOI10.1137/19M1253472MaRDI QIDQ5221262zbMATH OpenOpenAlexFDO

Authors Yeow Meng Chee, Duc Tu Dao, Han Mao Kiah, San Ling, Hengjia Wei

Publication date 25 March 2020

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1912.13301

zbMATH Keywords

Gray codesmaximum rank distance codesReed-Solomon codesrobust positioning patterns

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

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 amongst 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.

Recommendations

• Binary robust positioning patterns with low redundancy and efficient locating algorithms
• Robust positioning patterns
• Publication:4886137
• Position-based cryptography from noisy channels
• Searching with local constraints on error patterns

Cites work

• A method for constructing decodable de Bruijn sequences
• Constructions for perfect maps and pseudorandom arrays
• Error correcting sequence and projective de Bruijn graph
• Maximum-rank array codes and their application to crisscross error correction
• Minimum distance of logarithmic and fractional partial m-sequences
• Mutually uncorrelated codes for DNA storage
• Mutually Uncorrelated Primers for DNA-Based Data Storage
• Packing analogue of k-radius sequences
• Perfect maps
• Robust positioning patterns
• Simple and Robust Binary Self-Location Patterns
• The difference between consecutive primes. II
• Theory of codes with maximum rank distance

Cited in

(6)

• scientific article; zbMATH DE number 721894 (Why is no real title available?)
• Robust positioning patterns
• Robust Positioning of Service Units
• Binary robust positioning patterns with low redundancy and efficient locating algorithms
• Constructions of covering sequences and 2D-sequences
• Orientable sequences over non-binary alphabets

This page was built for publication: Robust positioning patterns with low redundancy

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5221262)