That would be interesting to investigate but you have to keep in mind that the centroids move between each iterations. So you have to re-build a new metric tree

That would be interesting to investigate but you have to keep in mind that the centroids move between each iterations. So you have to re-build a new metric tree at each iteration. kd-tree / build time complexity are between `n log(n)` and `n (log(n))^2`. You don't benefit from the classifical speed-up of metric trees where you build the tree once and then do many queries on the same tree. Also metric trees such as k-d tree and ball tree do no bring any speed-up in high dimensions.