2026-09-29T08:27:04Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10445 2026-09-23T06:34:49Z ddc:004 open_access

Journey to the Center of the Point Set Har-Peled, Sariel Jones, Mitchell Computational geometry Centerpoints Random walks We revisit an algorithm of Clarkson et al. [K. L. Clarkson et al., 1996], that computes (roughly) a 1/(4d^2)-centerpoint in O~(d^9) time, for a point set in R^d, where O~ hides polylogarithmic terms. We present an improved algorithm that computes (roughly) a 1/d^2-centerpoint with running time O~(d^7). While the improvements are (arguably) mild, it is the first progress on this well known problem in over twenty 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sariel Har-Peled and Mitchell Jones 2019 Is Part Of LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2019.41 urn:nbn:de:0030-drops-104454 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.41 eng https://creativecommons.org/licenses/by/3.0/legalcode