Enumerating all partitions induced by Voronoi diagrams for clustering

Question

a classical results by M. Inaba et al. in "Applications of Weighted Voronoi Diagrams and Randomization to Variance-Based k-CLustering" (Theorem 3) says

The number of Voronoi partitions of $n$ points by the Euclidean Voronoi diagram generated by $k$ points in $d$-dimensional space is $\mathcal{O}(n^{dk})$, and all the Voronoi partitions can be enumerated in $\mathcal{O}(n^{dk+1})$.

They basically divide the $d$-dimensional space into equivalence classes where two sets of center $\mu^1$ and $\mu^2$ are equivalent if they lead to the same Voronoi Diagram. Then they show that the arrangement of the $nk(k-1)/2$ surfaces

$$ \|x_i-\mu_j\|^2- \|x_i-\mu_{j'}\|^2 = 0 $$

for each point $x_i$ and two cluster center $\mu_j$ and $\mu_{j'}$ coincides with the equivalence relation from Voronoi partitions.

Next they argue that the combinatorial complexity of arrangements of $nk(k-1)/2$ constant-degree algebraic surfaces is bounded and that this implies and algorithm with running time $\mathcal{O}(n^{dk+1})$. Unfortunately, the cited source (Evaluation of combinatorial complexity for hypothesis spaces in learning theory with application, Master's Thesis, Department of Information Science, University of Toko, 1994) I cannot find anywhere. More precisely I cannot see the two following things.

1. Where can I find a bound for the combinatorial complexity of the arrangement of $nk(k-1)/2$ constant degree algebraic surfaces and
2. How does this help me to compute the arrangement?

For 2. I found the Bentley–Ottmann algorithm, however that only works for line segments and not degree 2 polynomials. How can this algorithm be generalized?

Thanks so much!

Answer 1

For results on the combinatorial complexity of arrangements (and other related results) a good reference is Chapter 28 of The Handbook of Discrete and Computational Geometry. In particular Theorem 28.1.4 specifies that the combinatorial complexity of an arrangement of $n$ constant-degree algebraic surfaces of dimension $d$ is $O(n^d)$.

Within the context of the paper $k$ is considered fixed, and therefore $nk(k-1)/2 = O(n)$. Further, in the paper the dimension of the vector space in the proof of Theorem 3 is $dk$. Thus, the complexity of the surface arrangement in the $dk$-dimensional vector space is $O(n^{dk})$. Note that if $k$ were not considered fixed (but still $O(n)$), then the complexity would have been $O((nk(k-1)/2)^{dk}) = O((n^3)^{dk}) = O(n^{3dk})$.

This answers your first question.

As for 2, the Bentley-Ottman algorithm can be generalized for any set of $x$-monotone curves (if the curves are not $x$-monotone, a splitting pre-process is required). The main difference from the case of line segments is to allow for more than a single intersection between curves and also for the possibility of tangent intersections.

This means that when the sweep-line algorithm passes an intersection point, it needs to check whether the order of the curves in the sweep-line structure should be swapped (a non-tangential intersection) or maintained (a tangential intersection). It also needs to check for the next intersection point between the adjacent curves, if it exists (since there can be more than a single intersection point).

CGAL-The Computational Geometry Algorithm Library, implements such a generic sweep-line algorithm in its arrangements package. It uses its "Traits" mechanism to implement the above requirements with implementations on circle arcs, conic sections, polynomials of any degree, and more. See the CGAL package documentation for further reference.