K. Zeger et Mr. Kantorovitz, AVERAGE NUMBER OF FACETS PER CELL IN TREE-STRUCTURED VECTOR QUANTIZERPARTITIONS, IEEE transactions on information theory, 39(3), 1993, pp. 1053-1055
Upper and lower bounds are derived for the average number of facets pe
r cell in the encoder partition of binary tree-structured vector quant
izers. The achievability of the bounds is described as well. It is sho
wn in particular that the average number of facets per cell for unbala
nced trees must lie asymptotically between 3 and 4 in R2, and each of
these bounds can be achieved, whereas for higher dimensions it is show
n that an arbitrarily large percentage of the cells can each have a li
near number (in codebook size) of facets. Analogous results are also i
ndicated for balanced trees.