|
|||||
|
|
Optimal tristance anticodes in certain graphs |
|
| Authors: | Tuvi Etzion Alexander Vardy |
| Institution: | a Technion — Israel Institute of Technology, Department of Computer Science, Technion City, Haifa 32000, Israel b Department of Computer Science, University of California San Diego, La Jolla, CA 92093, USA c Department of Electrical Engineering, University of California San Diego, La Jolla, CA 92093, USA d Department of Mathematics, University of California San Diego, La Jolla, CA 92093, USA |
| Abstract: | For z1,z2,z3∈Zn, the tristance d3(z1,z2,z3) is a generalization of the L1-distance on Zn to a quantity that reflects the relative dispersion of three points rather than two. A tristance anticodeAd of diameter d is a subset of Zn with the property that d3(z1,z2,z3)?d for all z1,z2,z3∈Ad. An anticode is optimal if it has the largest possible cardinality for its diameter d. We determine the cardinality and completely classify the optimal tristance anticodes in Z2 for all diameters d?1. We then generalize this result to two related distance models: a different distance structure on Z2 where d(z1,z2)=1 if z1,z2 are adjacent either horizontally, vertically, or diagonally, and the distance structure obtained when Z2 is replaced by the hexagonal lattice A2. We also investigate optimal tristance anticodes in Z3 and optimal quadristance anticodes in Z2, and provide bounds on their cardinality. We conclude with a brief discussion of the applications of our results to multi-dimensional interleaving schemes and to connectivity loci in the game of Go. |
| Keywords: | 05C12 05B40 94B25 |
| 本文献已被 ScienceDirect 等数据库收录！ | |