Category:Median cut algorithm
The median cut algorithm is a popular algorithm for color quantization, but can be applied to virtually any point clustering problem. In outline, it works as follows:
- Let B be a set of boxes containing points, initially containing only a single box containing all points.
- While the number of boxes in B is less than desired number of clusters...
- Find the largest side length of any side of any box.
- Cut that box into two boxes along its largest side in such a way that half the contained points fall into each new box.
- Shrink the two new boxes so that they are just large enough to contain their points.