  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.
