TY - GEN
T1 - Journey to the center of the point set
AU - Har-Peled, Sariel
AU - Jones, Mitchell
N1 - Publisher Copyright:
© Sariel Har-Peled and Mitchell Jones.
PY - 2019/6/1
Y1 - 2019/6/1
N2 - We revisit an algorithm of Clarkson et al. [1], that computes (roughly) a 1/(4d2)-centerpoint in Õ(d9) time, for a point set in ℝd, where Õ hides polylogarithmic terms. We present an improved algorithm that computes (roughly) a 1/d2-centerpoint with running time Õ(d7). 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.
AB - We revisit an algorithm of Clarkson et al. [1], that computes (roughly) a 1/(4d2)-centerpoint in Õ(d9) time, for a point set in ℝd, where Õ hides polylogarithmic terms. We present an improved algorithm that computes (roughly) a 1/d2-centerpoint with running time Õ(d7). 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.
KW - Centerpoints
KW - Computational geometry
KW - Random walks
UR - http://www.scopus.com/inward/record.url?scp=85068081374&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85068081374&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.SoCG.2019.41
DO - 10.4230/LIPIcs.SoCG.2019.41
M3 - Conference contribution
AN - SCOPUS:85068081374
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 35th International Symposium on Computational Geometry, SoCG 2019
A2 - Barequet, Gill
A2 - Wang, Yusu
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 35th International Symposium on Computational Geometry, SoCG 2019
Y2 - 18 June 2019 through 21 June 2019
ER -