### 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 IR^{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(log^{2} 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 language | English (US) |
---|---|

Title of host publication | Proceedings of the 9th Annual Symposium on Computational Geometry |

Publisher | Publ by ACM |

Pages | 91-98 |

Number of pages | 8 |

ISBN (Print) | 0897915828, 9780897915823 |

DOIs | |

State | Published - Jan 1 1993 |

Event | Proceedings of the 9th Annual Symposium on Computational Geometry - San Diego, CA, USA Duration: May 19 1993 → May 21 1993 |

### Publication series

Name | Proceedings of the 9th Annual Symposium on Computational Geometry |
---|

### Other

Other | Proceedings of the 9th Annual Symposium on Computational Geometry |
---|---|

City | San Diego, CA, USA |

Period | 5/19/93 → 5/21/93 |

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

## Cite this

*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