The pairwise nearest neighbor (PNN) algorithm is a well-known method for th
e codebook construction in vector quantization and for the clustering of da
ta sets. The algorithm has a simple structure and it provides high quality
solutions. A drawback of the method is the large running time of the origin
al (exact) implementation. We prove the monotony of the merge costs of the
PNN. The monotony property is utilized to speed up an existing PNN variant.
The idea is to postpone a number of distance calculations. In this way, we
can reduce the computation by about 35% while preserving the exactness of
the PNN, (C) 1999 Society of Photo-Optical Instrumentation Engineers. [S009
1-3286(99)01411-7].