Journey to the Center of the Point Set

Sariel Har-Peled, Mitchell Jones

Research output: Contribution to journalArticlepeer-review


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 languageEnglish (US)
Article number3431285
JournalACM Transactions on Algorithms
Issue number1
StatePublished - Jan 2021


  • Computational geometry
  • centerpoints
  • random walks

ASJC Scopus subject areas

  • Mathematics (miscellaneous)


Dive into the research topics of 'Journey to the Center of the Point Set'. Together they form a unique fingerprint.

Cite this