文章基本信息

标题：Journey to the Center of the Point Set
本地全文：下载
作者：Sariel Har-Peled ; Mitchell Jones
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2019
卷号：129
页码：1-14
DOI：10.4230/LIPIcs.SoCG.2019.41
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Computational geometry; Centerpoints; Random walks