Journey to the Center of the Point Set

Sariel Har-Peled, Mitchell Jones

Research output: Contribution to journalArticlepeer-review

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

Keywords

  • centerpoints
  • Computational geometry
  • random walks

ASJC Scopus subject areas

  • Mathematics (miscellaneous)

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

Cite this