Computing the Center Region and Its Variants

Abstract

We present an $O(n^2{\log }^{4}n)$-time algorithm for computing the center region of a set of $n$ points in the three-dimensional Euclidean space. This improves the previously best known algorithm by Agarwal, Sharir and Welzl, which takes $O(n^{2+\epsilon })$ time for any $\epsilon >0$. It is known that the combinatorial complexity of the center region is $\Omega (n^2)$ in the worst case, thus our algorithm is almost tight. We also consider the problem of computing a colored version of the center region in the two-dimensional Euclidean space and present an $O(n{\log }^{4}n)$-time algorithm.