The beta version of DROPS 2 is now publicly available! Check this page out at DROPS 2 now!


License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2019.41
URN: urn:nbn:de:0030-drops-104454
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10445/
Go to the corresponding LIPIcs Volume Portal

Har-Peled, Sariel ; Jones, Mitchell

Journey to the Center of the Point Set

pdf-format:
LIPIcs-SoCG-2019-41.pdf (0.6 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{harpeled_et_al:LIPIcs:2019:10445,
  author =	{Sariel Har-Peled and Mitchell Jones},
  title =	{{Journey to the Center of the Point Set}},
  booktitle =	{35th International Symposium on Computational Geometry (SoCG 2019)},
  pages =	{41:1--41:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-104-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{129},
  editor =	{Gill Barequet and Yusu Wang},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10445},
  URN =		{urn:nbn:de:0030-drops-104454},
  doi =		{10.4230/LIPIcs.SoCG.2019.41},
  annote =	{Keywords: Computational geometry, Centerpoints, Random walks}
}

Keywords: Computational geometry, Centerpoints, Random walks
Collection: 35th International Symposium on Computational Geometry (SoCG 2019)
Issue Date: 2019
Date of publication: 11.06.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI