[IEEE Trans. on Information Theory, September 1994, pp. 1647-1649]
Number of Nearest Neighbors in a Euclidean Code
Kenneth Zeger and Allen Gersho
Abstract
A Euclidean code is a finite set of points in n-dimensional Euclidean space, $R^n$.
The total number of nearest neighbors of a given codepoint in the code
is called its touching number. We show that the maximum number of codepoints
$F_n$ that can share the same nearest neighbor codepoint is equal to the
maximum kissing number $\tau_n$ in n dimensions, that is, the maximum number
of unit spheres that can touch a given unit sphere without overlapping. We
then apply a known upper bound on $\tau_n$ to obtain
$F_n \leq 2^{n(0.401 + o(1))}$,
which improves upon the best known upper bound of
$F_n \leq 2^{n(1+o(1))}$. We also show that the average touching number T
of all the points in a Euclidean code is upper bounded by $\tau_n$.