This question is a followup question to this one.
Variance-based $k$-clustering is the problem of finding a clustering of $n$ points from $\mathbb{R}^d$ into $k$ clusters such that the intra-cluster variance is minimized (also known as $k$-means). It is well known that any optimal $k$-clustering is a Voronoi partition by the euclidean Voronoi diagram associated with the means of the clusters. In [1], it is shown that the number of Voronoi partitions of $n$ points of $\mathbb{R}^d$ into $k$ clusters is bounded by $\mathcal{O}(n^{kd})$. It is concluded that the $k$-clustering problem can solved in time $\mathcal{O}(n^{dk+1})$ by simply enumerating all Voronoi partitions. In a very similar (but much less cited) article by the same authors (I think it is just a journal version of [1]) this claim is no longer being made [2]. Instead, it is stated that the Voronoi partitions can be enumerated in $\mathcal{O}(n^{dk+k-d-2})$ with a reference to [3] which I cannot find anywhere.
From my understanding the technique is as follows: The Voronoi partitions correspond to the arrangement of some algebraic surfaces in $\mathbb{R}^{dk}$ (Theorem 3 of [2]) and the complexity of this arrangement is bounded by $\mathcal{O}(n^{dk})$. These algebraic surfaces can be linearized to obtain hyperplanes and the arrangement of these hyperplanes can be computed in order to enumerate Voronoi partitions. But I am not sure if this is correct.
My question: How to enumerate all Voronoi partitions? Is it really necessary to study the arrangement of surfaces in a $kd$-dimensional space? An if yes, is there any reference that describes how to compute this arrangement?
My intuition is that the arrangement of the surfaces in this higher dimensional space can be much more complex than the set of all Voroni partitions...
The answer to the mathoverflow question mention on top is very helpful but does not fully answer the question. Both the literature and software recommendation focus on 2 and 3-dimensional arrangements. However, even for the simplest non-trivial case $k=2$ and $d=2$ we are dealing with a 4-dimensional space.
[1] Inaba, Mary, Naoki Katoh, and Hiroshi Imai. "Applications of weighted Voronoi diagrams and randomization to variance-based k-clustering." Proceedings of the tenth annual symposium on Computational geometry. 1994.
[2] Inaba, Mary, Naoki Katoh, and Hiroshi Imai. "Variance-based k-clustering algorithms by Voronoi diagrams and randomization." IEICE Transactions on Information and Systems 83.6 (2000): 1199-1206.
[3] M. Inaba and H. Imai, “The number of partitions of n points induced by the Voronoi diagram via the conjugacy generated by k points,” “Proc. 1st Japanese-Hungarian Symp. on Discrete Mathematics and Its Applications, pp.83–90, Kyoto, March 1999.
