{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:22:05Z","timestamp":1750220525034,"version":"3.41.0"},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2020,12,31]],"date-time":"2020-12-31T00:00:00Z","timestamp":1609372800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF AF","award":["CCF-1421231 and CCF-1217462"],"award-info":[{"award-number":["CCF-1421231 and CCF-1217462"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2021,1,31]]},"abstract":"<jats:p>\n            Let\n            <jats:italic>P<\/jats:italic>\n            be a set of\n            <jats:italic>n<\/jats:italic>\n            points in R\n            <jats:sup>\n              <jats:italic>d<\/jats:italic>\n            <\/jats:sup>\n            . For a parameter \u03b1 \u2208 (0,1), an \u03b1-centerpoint of\n            <jats:italic>P<\/jats:italic>\n            is a point\n            <jats:italic>p<\/jats:italic>\n            \u2208 R\n            <jats:sup>\n              <jats:italic>d<\/jats:italic>\n            <\/jats:sup>\n            such that all closed halfspaces containing\n            <jats:italic>P<\/jats:italic>\n            also contain at least \u03b1\n            <jats:italic>n<\/jats:italic>\n            points of\n            <jats:italic>P<\/jats:italic>\n            . We revisit an algorithm of Clarkson et\u00a0al. [1996] that computes (roughly) a 1\/(4\n            <jats:italic>d<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            )-centerpoint in \u00d5(\n            <jats:italic>d<\/jats:italic>\n            <jats:sup>9<\/jats:sup>\n            ) randomized time, where \u00d5 hides polylogarithmic terms. We present an improved algorithm that can compute centerpoints with quality arbitrarily close to 1\/\n            <jats:italic>d<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            and runs in randomized time \u00d5(\n            <jats:italic>d<\/jats:italic>\n            <jats:sup>7<\/jats:sup>\n            ). While the improvements are (arguably) mild, it is the first refinement of the algorithm by Clarkson et\u00a0al. [1996] in over 20 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.\n          <\/jats:p>","DOI":"10.1145\/3431285","type":"journal-article","created":{"date-parts":[[2020,12,31]],"date-time":"2020-12-31T18:48:01Z","timestamp":1609440481000},"page":"1-21","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Journey to the Center of the Point Set"],"prefix":"10.1145","volume":"17","author":[{"given":"Sariel","family":"Har-Peled","sequence":"first","affiliation":[{"name":"University of Illinois at Urbana-Champaign, Urbana, IL"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2971-398X","authenticated-orcid":false,"given":"Mitchell","family":"Jones","sequence":"additional","affiliation":[{"name":"University of Illinois at Urbana-Champaign, Urbana, IL"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,12,31]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms(SODA\u201904)","author":"Chan Timothy M.","year":"2004","unstructured":"Timothy M. Chan . 2004 . An optimal randomized algorithm for maximum Tukey depth . In Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms(SODA\u201904) , J. Ian Munro (Ed.). SIAM, Philadelphia, PA, 430--436. Retrieved from http:\/\/dl.acm.org\/citation.cfm?id=982792.982853. Timothy M. Chan. 2004. An optimal randomized algorithm for maximum Tukey depth. In Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms(SODA\u201904), J. Ian Munro (Ed.). SIAM, Philadelphia, PA, 430--436. Retrieved from http:\/\/dl.acm.org\/citation.cfm?id=982792.982853."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1142\/S021819599600023X"},{"key":"e_1_2_1_3_1","volume-title":"Dubhashi and Alessandro Panconesi","author":"Devdatt","year":"2009","unstructured":"Devdatt P. Dubhashi and Alessandro Panconesi . 2009 . Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press . Retrieved from http:\/\/www.cambridge.org\/gb\/knowledge\/isbn\/item2327542\/. Devdatt P. Dubhashi and Alessandro Panconesi. 2009. Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press. Retrieved from http:\/\/www.cambridge.org\/gb\/knowledge\/isbn\/item2327542\/."},{"volume-title":"An Introduction to Nonsmooth Analysis","author":"Ferrera Juan","key":"e_1_2_1_4_1","unstructured":"Juan Ferrera . 2013. An Introduction to Nonsmooth Analysis . Academic Press , Boston, MA . DOI:https:\/\/doi.org\/10.1016\/C2013-0-15234-8 10.1016\/C2013-0-15234-8 Juan Ferrera. 2013. An Introduction to Nonsmooth Analysis. Academic Press, Boston, MA. DOI:https:\/\/doi.org\/10.1016\/C2013-0-15234-8"},{"volume-title":"Geometric Approximation Algorithms. Math. Surveys 8 Monographs","author":"Har-Peled Sariel","key":"e_1_2_1_5_1","unstructured":"Sariel Har-Peled . 2011. Geometric Approximation Algorithms. Math. Surveys 8 Monographs , Vol. 173 . Amer. Math. Soc., Boston, MA. DOI :https:\/\/doi.org\/10.1090\/surv\/173 10.1090\/surv Sariel Har-Peled. 2011. Geometric Approximation Algorithms. Math. Surveys 8 Monographs, Vol. 173. Amer. Math. Soc., Boston, MA. DOI:https:\/\/doi.org\/10.1090\/surv\/173"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 35th International Annual Symposium on Computer Geometry (SoCG\u201919)","author":"Har-Peled Sariel","year":"2019","unstructured":"Sariel Har-Peled and Mitchell Jones . 2019 . Journey to the center of the point set . In Proceedings of the 35th International Annual Symposium on Computer Geometry (SoCG\u201919) . Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Wadern, Germany, 41:1--41:14. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.SoCG. 2019.41 10.4230\/LIPIcs.SoCG.2019.41 Sariel Har-Peled and Mitchell Jones. 2019. Journey to the center of the point set. In Proceedings of the 35th International Annual Symposium on Computer Geometry (SoCG\u201919). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Wadern, Germany, 41:1--41:14. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.SoCG.2019.41"},{"key":"e_1_2_1_7_1","unstructured":"Sariel Har-Peled and Mitchell Jones. 2019. Where is the center of Illinois? Retrieved from https:\/\/www.youtube.com\/watch?v=NoSvqRGAYYY.  Sariel Har-Peled and Mitchell Jones. 2019. Where is the center of Illinois? Retrieved from https:\/\/www.youtube.com\/watch?v=NoSvqRGAYYY."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/3116271.3116497"},{"key":"e_1_2_1_9_1","unstructured":"Sariel Har-Peled and Timothy Zhou. 2020. Improved Approximation Algorithms for Tverberg Partitions. Retrieved from http:\/\/arxiv.org\/abs\/2007.08717.  Sariel Har-Peled and Timothy Zhou. 2020. Improved Approximation Algorithms for Tverberg Partitions. Retrieved from http:\/\/arxiv.org\/abs\/2007.08717."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187876"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.spl.2017.11.017"},{"key":"e_1_2_1_12_1","unstructured":"Chaya Keller Shakhar Smorodinsky and G\u00e1bor Tardos. 2015. Improved bounds on the Hadwiger-Debrunner numbers. Retrieved from https:\/\/arxiv.org\/abs\/1512.04026.  Chaya Keller Shakhar Smorodinsky and G\u00e1bor Tardos. 2015. Improved bounds on the Hadwiger-Debrunner numbers. Retrieved from https:\/\/arxiv.org\/abs\/1512.04026."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.148"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1741"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1018"},{"volume-title":"Lectures on Discrete Geometry. Grad. Text in Math","author":"Matou\u0161ek Ji\u0159\u00ed","key":"e_1_2_1_16_1","unstructured":"Ji\u0159\u00ed Matou\u0161ek . 2002. Lectures on Discrete Geometry. Grad. Text in Math ., Vol. 212 . Springer , Berlin . DOI:https:\/\/doi.org\/10.1007\/978-1-4613-0039-7\/ 10.1007\/978-1-4613-0039-7 Ji\u0159\u00ed Matou\u0161ek. 2002. Lectures on Discrete Geometry. Grad. Text in Math., Vol. 212. Springer, Berlin. DOI:https:\/\/doi.org\/10.1007\/978-1-4613-0039-7\/"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/3115953.3116001"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.87"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2010.04.006"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-013-9528-7"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2007.02.006"},{"key":"e_1_2_1_22_1","volume-title":"Mustafa and Kasturi Varadarajan","author":"Nabil","year":"2017","unstructured":"Nabil H. Mustafa and Kasturi Varadarajan . 2017 . Epsilon-approximations and epsilon-nets. Retrieved from http:\/\/arxiv.org\/abs\/1702.03676. Nabil H. Mustafa and Kasturi Varadarajan. 2017. Epsilon-approximations and epsilon-nets. Retrieved from http:\/\/arxiv.org\/abs\/1702.03676."},{"key":"e_1_2_1_23_1","first-page":"291","article-title":"A theorem on general measure","volume":"21","author":"Rado Richard","year":"1947","unstructured":"Richard Rado . 1947 . A theorem on general measure . J. Lond. Math. Soc. 21 (1947), 291 -- 300 . Richard Rado. 1947. A theorem on general measure. J. Lond. Math. Soc. 21 (1947), 291--300.","journal-title":"J. Lond. Math. Soc."},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the 32nd International Annual Symposium on Computer Geometry (SoCG). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik","author":"Rok Alexandre","year":"2016","unstructured":"Alexandre Rok and Shakhar Smorodinsky . 2016 . Weak 1\/r-nets for moving points . In Proceedings of the 32nd International Annual Symposium on Computer Geometry (SoCG). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik , Wadern, Germany, 59:1--59:13. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.SoCG. 2016.59 10.4230\/LIPIcs.SoCG.2016.59 Alexandre Rok and Shakhar Smorodinsky. 2016. Weak 1\/r-nets for moving points. In Proceedings of the 32nd International Annual Symposium on Computer Geometry (SoCG). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Wadern, Germany, 59:1--59:13. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.SoCG.2016.59"},{"key":"e_1_2_1_25_1","unstructured":"David Rolnick and Pablo Sober\u00f3n. 2016. Algorithms for Tverberg\u2019s theorem via centerpoint theorems. Retrieved from http:\/\/arxiv.org\/abs\/1601.03083.  David Rolnick and Pablo Sober\u00f3n. 2016. Algorithms for Tverberg\u2019s theorem via centerpoint theorems. Retrieved from http:\/\/arxiv.org\/abs\/1601.03083."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00030"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/1116025"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3431285","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3431285","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:24:46Z","timestamp":1750195486000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3431285"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,12,31]]},"references-count":27,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,1,31]]}},"alternative-id":["10.1145\/3431285"],"URL":"https:\/\/doi.org\/10.1145\/3431285","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2020,12,31]]},"assertion":[{"value":"2019-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-12-31","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}