Two-Dimensional Patterns With Distinct Differences—Constructions, Bounds, and Maximal Anticodes
From MaRDI portal
Publication:5281579
DOI10.1109/TIT.2009.2039046zbMATH Open1366.94658arXiv0811.3832MaRDI QIDQ5281579FDOQ5281579
Authors: Simon R. Blackburn, Tuvi Etzion, Maura Paterson, Keith M. Martin 
Publication date: 27 July 2017
Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)
Abstract: A two-dimensional grid with dots is called a emph{configuration with distinct differences} if any two lines which connect two dots are distinct either in their length or in their slope. These configurations are known to have many applications such as radar, sonar, physical alignment, and time-position synchronization. Rather than restricting dots to lie in a square or rectangle, as previously studied, we restrict the maximum distance between dots of the configuration; the motivation for this is a new application of such configurations to key distribution in wireless sensor networks. We consider configurations in the hexagonal grid as well as in the traditional square grid, with distances measured both in the Euclidean metric, and in the Manhattan or hexagonal metrics. We note that these configurations are confined inside maximal anticodes in the corresponding grid. We classify maximal anticodes for each diameter in each grid. We present upper bounds on the number of dots in a pattern with distinct differences contained in these maximal anticodes. Our bounds settle (in the negative) a question of Golomb and Taylor on the existence of honeycomb arrays of arbitrarily large size. We present constructions and lower bounds on the number of dots in configurations with distinct differences contained in various two-dimensional shapes (such as anticodes) by considering periodic configurations with distinct differences in the square grid.
Full work available at URL: https://arxiv.org/abs/0811.3832
Recommendations
- Maximal pattern complexity of two-dimensional words
- Two dimensional constacyclic codes of arbitrary length over finite fields
- On the largest dimension of anticodes
- Two-dimensional weight-constrained codes through enumeration bounds
- Exponential numbers of two-weight codes, difference sets and symmetric designs
- Complexity of sets of two-dimensional patterns
- An application of difference sets to a problem concerning graphical codes
- Efficient code constructions for certain two-dimensional constraints
- On the Complexity of Computing the Capacity of Codes That Avoid Forbidden Difference Patterns
- A family of two-dimensional words with maximal pattern complexity \(2k\)
Cited In (2)
This page was built for publication: Two-Dimensional Patterns With Distinct Differences—Constructions, Bounds, and Maximal Anticodes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5281579)
