Optimal Tristance Anticodes in Certain Graphs

Abstract

For $z_1,z_2,z_3\in {\mathbb{Z}}^n$, the \emph{tristance} $d_3(z_1,z_2,z_3)$ is a generalization of the $L_1$-distance on ${\mathbb{Z}}^n$ to a quantity that reflects the relative dispersion of three points rather than two. A tristance anticode $\cA_d$ of diameter $d$ is a subset of ${\mathbb{Z}}^n$ with the property that $d_3(z_1,z_2,z_3)\le d$ for all $z_1,z_2,z_3 \in \cA_d$. 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 ${\mathbb{Z}}^2$ for all diameters $d\ge 1$. We then generalize this result to two related distance models: a different distance structure on ${\mathbb{Z}}^2$ where $d(z_1,z_2)=1$ if $z_1,z_2$ are adjacent either horizontally, vertically, or diagonally, and the distance structure obtained when ${\mathbb{Z}}^2$ is replaced by the hexagonal lattice $A_2$. We also investigate optimal tristance anticodes in ${\mathbb{Z}}^3$ and optimal quadristance anticodes in ${\mathbb{Z}}^2$, 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.

33 pages, 12 figures