Computing the center region and its variants

Abstract

We present an O(n2 log4 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(n2+��) time for any �� > 0. It is known that the complexity of the center region is ��(n2), thus our algorithm is almost tight. The second problem we consider is computing a colored version of the center region in the two-dimensional Euclidean space. We present an O(n log4 n)-time algorithm for this problem. ? Springer International Publishing AG 2017.