## Abstract

Let P be a set of n points in R d. For a parameter α (0,1), an α-centerpoint of P is a point p R d such that all closed halfspaces containing P also contain at least α n points of P. We revisit an algorithm of Clarkson et al. [1996] that computes (roughly) a 1/(4d)-centerpoint in Õ(d) randomized time, where Õ hides polylogarithmic terms. We present an improved algorithm that can compute centerpoints with quality arbitrarily close to 1/d and runs in randomized time Õ(d). While the improvements are (arguably) mild, it is the first refinement of the algorithm by Clarkson et al. [1996] in over 20 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.

Original language | English (US) |
---|---|

Article number | 3431285 |

Journal | ACM Transactions on Algorithms |

Volume | 17 |

Issue number | 1 |

DOIs | |

State | Published - Jan 2021 |

## Keywords

- Computational geometry
- centerpoints
- random walks

## ASJC Scopus subject areas

- Mathematics (miscellaneous)