Approximating center points with iterated radon points

K. L. Clarkson, David Eppstein, Gary L. Miller, Carl Sturtivant, Shang Hua Teng

Research output: Chapter in Book/Report/Conference proceedingConference contribution

21 Scopus citations

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.

Original languageEnglish (US)
Title of host publicationProceedings of the 9th Annual Symposium on Computational Geometry
PublisherPubl by ACM
Pages91-98
Number of pages8
ISBN (Print)0897915828, 9780897915823
DOIs
StatePublished - Jan 1 1993
EventProceedings of the 9th Annual Symposium on Computational Geometry - San Diego, CA, USA
Duration: May 19 1993May 21 1993

Publication series

NameProceedings of the 9th Annual Symposium on Computational Geometry

Other

OtherProceedings of the 9th Annual Symposium on Computational Geometry
CitySan Diego, CA, USA
Period5/19/935/21/93

Fingerprint Dive into the research topics of 'Approximating center points with iterated radon points'. Together they form a unique fingerprint.

  • Cite this

    Clarkson, K. L., Eppstein, D., Miller, G. L., Sturtivant, C., & Teng, S. H. (1993). Approximating center points with iterated radon points. In Proceedings of the 9th Annual Symposium on Computational Geometry (pp. 91-98). (Proceedings of the 9th Annual Symposium on Computational Geometry). Publ by ACM. https://doi.org/10.1145/160985.161004