Approximating center points with iterated radon points
Kenneth L. Clarkson, David Eppstein, Gary Lee Miller, Carl Sturtivant, Shang‐Hua Teng · 1993
We describe a practical and provably good algorithm for approximating center points in any number of dimensions. Here c is a center point of a point set P in ℝd if every closed halfspace containing c contains at least |P|/(d+1) points of P. Our algorithm has a small constant factor and is the first approximate center point algorithm whose complexity is subexponential in d. Moreover, it can be optimally parallelized to require O(log2 d loglog n) time. Our algorithm has been used in mesh partitioning methods, and has the potential to improve results in practice for constructing weak ε-nets and other geometric algorithms. We derive a variant of our algorithm with a time bound fully polynomial in d, and show how to combine our approach with previous techniques to compute high quality center points more quickly.