乐胖代购免代理版

{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T13:16:54Z","timestamp":1740143814933,"version":"3.37.3"},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","issue":"1","funder":[{"name":"NSF AF","award":["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":"\n Let\n P<\/jats:italic>\n be a set of\n n<\/jats:italic>\n points in R\n \n d<\/jats:italic>\n <\/jats:sup>\n . For a parameter \u03b1 \u2208 (0,1), an \u03b1-centerpoint of\n P<\/jats:italic>\n is a point\n p<\/jats:italic>\n \u2208 R\n \n d<\/jats:italic>\n <\/jats:sup>\n such that all closed halfspaces containing\n P<\/jats:italic>\n also contain at least \u03b1\n n<\/jats:italic>\n points of\n P<\/jats:italic>\n . We revisit an algorithm of Clarkson et\u00a0al. [1996] that computes (roughly) a 1\/(4\n d<\/jats:italic>\n 2<\/jats:sup>\n )-centerpoint in \u00d5(\n d<\/jats:italic>\n 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 d<\/jats:italic>\n 2<\/jats:sup>\n and runs in randomized time \u00d5(\n d<\/jats:italic>\n 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":1,"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"}]},{"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"}]}],"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\/pdf\/10.1145\/3431285","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T19:20:27Z","timestamp":1672600827000},"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"}}]}}