[IEEE Trans. on Information Theory, May 1993, pp. 1053-1055]
Average Number of Facets per Cell in Tree-Structured
Vector Quantizer Partitions
Kenneth Zeger & Miriam R. Kantorovitz
Abstract
Upper and lower bounds are derived for the average number of facets per cell in
the encoder partition of binary Tree-Structured Vector Quantizers. The
achievability of the bounds is described as well. It is shown in particular
that the average number of facets per cell for unbalanced trees must lie
asymptotically between 3 and 4 in R^2, and each of these bounds can be
achieved, whereas for higher dimensions it is shown that an arbitrarily large
percentage of the cells can have a linear number (in codebook size) of facets.
Analogous results are also indicated for balanced trees.