@article{30c3458ea62d4bc7a76d3b87b45ab817,
title = "Journey to the Center of the Point Set",
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 {\~O}(d) randomized time, where {\~O} hides polylogarithmic terms. We present an improved algorithm that can compute centerpoints with quality arbitrarily close to 1/d and runs in randomized time {\~O}(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.",
keywords = "Computational geometry, centerpoints, random walks",
author = "Sariel Har-Peled and Mitchell Jones",
note = "Funding Information: A preliminary version of this work appeared in SoCG 2019 [6]. Work on this article was partially supported by NSF AF Awards No. CCF-1421231 and No. CCF-1217462. Authors{\textquoteright} address: S. Har-Peled and M. Jones, University of Illinois at Urbana-Champaign, 201 N. Goodwin Avenue, Urbana, IL, 61801; emails: {sariel, mfjones2}@illinois.edu. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org. {\textcopyright} 2020 Association for Computing Machinery. 1549-6325/2020/12-ART9 $15.00 https://doi.org/10.1145/3431285 Publisher Copyright: {\textcopyright} 2020 ACM.",
year = "2021",
month = jan,
doi = "10.1145/3431285",
language = "English (US)",
volume = "17",
journal = "ACM Transactions on Algorithms",
issn = "1549-6325",
publisher = "Association for Computing Machinery",
number = "1",
}