LIPIcs.SoCG.2019.41.pdf
- Filesize: 0.55 MB
- 14 pages
Document
Journey to the Center of the Point Set
Authors
-
Part of:
Volume:
35th International Symposium on Computational Geometry (SoCG 2019)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Computational Geometry (SoCG) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2019-06-11
Cite As Get BibTex
Sariel Har-Peled and Mitchell Jones. Journey to the Center of the Point Set. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 41:1-41:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.SoCG.2019.41
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.
Subject Classification
ACM Subject Classification
- Theory of computation → Computational geometry
- Theory of computation → Random walks and Markov chains
Keywords
- Computational geometry
- Centerpoints
- Random walks
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- K. L. Clarkson, D. Eppstein, G. L. Miller, C. Sturtivant, and S.-H. Teng. Approximating center points with iterative Radon points. Internat. J. Comput. Geom. Appl., 6:357-377, 1996. URL: http://cm.bell-labs.com/who/clarkson/center.html.
- S. Har-Peled. Geometric Approximation Algorithms, volume 173 of Math. Surveys &Monographs. Amer. Math. Soc., Boston, MA, USA, 2011. URL: http://dx.doi.org/10.1090/surv/173.
- S. Har-Peled and M. Sharir. Relative (p,ε)-Approximations in Geometry. Discrete Comput. Geom., 45(3):462-496, 2011. URL: http://dx.doi.org/10.1007/s00454-010-9248-1.
- Sariel Har-Peled and Mitchell Jones. Journey to the Center of the Point Set. CoRR, abs/1712.02949, 2019. URL: http://arxiv.org/abs/1712.02949.
- D. Haussler and E. Welzl. ε-nets and simplex range queries. Discrete Comput. Geom., 2:127-151, 1987. URL: http://dx.doi.org/10.1007/BF02187876.
- C. Keller, S. Smorodinsky, and G. Tardos. Improved bounds on the Hadwiger-Debrunner numbers. ArXiv e-prints, December 2015. URL: http://arxiv.org/abs/1512.04026.
- C. Keller, S. Smorodinsky, and G. Tardos. On Max-Clique for intersection graphs of sets and the Hadwiger-Debrunner numbers. In Philip N. Klein, editor, Proc. 28th ACM-SIAM Sympos. Discrete Algs. (SODA), pages 2254-2263. SIAM, 2017. URL: http://dx.doi.org/10.1137/1.9781611974782.148.
-
Y. Li, P. M. Long, and A. Srinivasan. Improved Bounds on the Sample Complexity of Learning. J. Comput. Syst. Sci., 62(3):516-527, 2001.
- J. Matoušek. Lectures on Discrete Geometry, volume 212 of Grad. Text in Math. Springer, 2002. URL: http://dx.doi.org/10.1007/978-1-4613-0039-7/.
- J. Matoušek and U. Wagner. New Constructions of Weak epsilon-Nets. Discrete Comput. Geom., 32(2):195-206, 2004. URL: http://www.springerlink.com/index/10.1007/s00454-004-1116-4.
- G. L. Miller and D. R. Sheehy. Approximate centerpoints with proofs. Comput. Geom., 43(8):647-654, 2010. URL: http://dx.doi.org/10.1016/j.comgeo.2010.04.006.
- N. H. Mustafa and S. Ray. Weak ε-nets have basis of size O(ε^-1 log ε^-1) in any dimension. Comput. Geom. Theory Appl., 40(1):84-91, 2008. URL: http://dx.doi.org/10.1016/j.comgeo.2007.02.006.
- N. H. Mustafa and K. Varadarajan. Epsilon-approximations and epsilon-nets. CoRR, abs/1702.03676, 2017. URL: http://arxiv.org/abs/1702.03676.
- A. Rok and S. Smorodinsky. Weak 1/r-Nets for Moving Points. In Proc. 32nd Int. Annu. Sympos. Comput. Geom. (SoCG), pages 59:1-59:13, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.SoCG.2016.59.
- N. Rubin. An Improved Bound for Weak Epsilon-Nets in the Plane. In Proc. 59th Annu. Sympos. on Found. of Comput. Sci., (FOCS), pages 224-235, 2018. URL: http://dx.doi.org/10.1109/FOCS.2018.00030.
-
V. N. Vapnik and A. Y. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory Probab. Appl., 16:264-280, 1971.