Computing the Center Region and Its Variants

2019/10/27 by Oh, Eunjin, Ahn, Hee-Kap
#Computational Geometry (cs.CG) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1910.12169

Abstract

We present an O(n²log⁴ 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+ε) time for any ε> 0. It is known that the combinatorial complexity of the center region is Ω(n²) 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(nlog⁴ n)-time algorithm.

Related

• Journey to the Center of the Point Set
• The 2-Center Problem in Three Dimensions
• Efficient Algorithms for One-Dimensional k-Center Problems
• An Efficient Algorithm for 2D Euclidean 2-Center with Outliers
• Efficient Planar Two-Center Algorithms