Journey to the Center of the Point Set

2017/12/08 by Har-Peled, Sariel, Jones, Mitchell
#Computational Geometry (cs.CG) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1712.02949

Abstract

\renewcommand\Reℝ \newcommand\epsε \newcommand\NetS \newcommand\tldO\widetildeO \newcommand\bodyC We revisit an algorithm of Clarkson etal [CEMST96], that computes (roughly) a 1/(4d²)-centerpoint in \tldO(d⁹) time, for a point set in \Re^d, where \tldO hides polylogarithmic terms. We present an improved algorithm that computes (roughly) a 1/d²-centerpoint with running time \tldO(d⁷). While the improvements are (arguably) mild, it is the first progress on this well known problem in over twenty years. The new algorithm is simpler, and the running time bound follows by a simple random walk argument, which we believe to be of independent interest. We also present several new applications of the improved centerpoint algorithm.

Related

• Computing the Center Region and Its Variants
• Improved Approximation Algorithms for Tverberg Partitions
• Optimal Algorithms for Geometric Centers and Depth
• Tight Lower Bounds for Approximate & Exact k-Center in ℝ^d
• Efficient Algorithms for One-Dimensional k-Center Problems