How many points in Euclidean space can have a common nearest neighbor?
K. Zeger, A. Gersho · 2002
An Euclidean code is a finite set of codepoints in n-dimensional Euclidean space, /spl Rscr//sup 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/sub n/ that can share the same nearest neighbor codepoint is equal to the maximum kissing number /spl tau//sub 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 /spl tau//sub n/ to obtain F/sub n//spl les/2/sup n(0.401+/spl ogr/(1))/, which improves upon the best known upper bound of F/sub n//spl les/2/sup n(1+/spl ogr/(1))/. We also show that the average touching number of all the points in an Euclidean code is upper bounded by /spl tau//sub n/.>