AVERAGE NUMBER OF FACETS PER CELL IN TREE-STRUCTURED VECTOR QUANTIZERPARTITIONS

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.