@inproceedings{9a701408d8ba4937b79b1d40176c84fe,

title = "Approximating center points with iterated radon points",

abstract = "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 IRd 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 log log 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.",

author = "Clarkson, {K. L.} and David Eppstein and Miller, {Gary L.} and Carl Sturtivant and Teng, {Shang Hua}",

year = "1993",

doi = "10.1145/160985.161004",

language = "English (US)",

isbn = "0897915828",

series = "Proceedings of the 9th Annual Symposium on Computational Geometry",

publisher = "Publ by ACM",

pages = "91--98",

booktitle = "Proceedings of the 9th Annual Symposium on Computational Geometry",

note = "Proceedings of the 9th Annual Symposium on Computational Geometry ; Conference date: 19-05-1993 Through 21-05-1993",

}