{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:22:46Z","timestamp":1750306966776,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":33,"publisher":"ACM","license":[{"start":{"date-parts":[[2013,6,1]],"date-time":"2013-06-01T00:00:00Z","timestamp":1370044800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2013,6]]},"DOI":"10.1145\/2488608.2488684","type":"proceedings-article","created":{"date-parts":[[2013,5,28]],"date-time":"2013-05-28T16:35:41Z","timestamp":1369758941000},"page":"605-614","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Net and prune"],"prefix":"10.1145","author":[{"given":"Sariel","family":"Har-Peled","sequence":"first","affiliation":[{"name":"University of Illinois Urbana Champaign, Urbana, IL, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Benjamin Adam","family":"Raichel","sequence":"additional","affiliation":[{"name":"University of Illinois Urbana Champaign, Urbana, IL, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2013,6]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1008731.1008736"},{"key":"e_1_3_2_1_2_1","volume-title":"Math. Sci. Research Inst. Pub","author":"Agarwal P. K.","year":"2005","unstructured":"P. K. Agarwal , S. Har-Peled , and K. Varadarajan . Geometric approximation via coresets. In J. E. Goodman, J. Pach, and E. Welzl, editors, Combinatorial and Computational Geometry , Math. Sci. Research Inst. Pub . Cambridge , 2005 . P. K. Agarwal, S. Har-Peled, and K. Varadarajan. Geometric approximation via coresets. In J. E. Goodman, J. Pach, and E. Welzl, editors, Combinatorial and Computational Geometry, Math. Sci. Research Inst. Pub. Cambridge, 2005."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1798596.1798602"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1994.1038"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0114-7"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1983.16"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-012-9402-z"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8655(93)90141-Y"},{"key":"e_1_3_2_1_9_1","unstructured":"A. Ene B. Raichel and S. Har-Peled. Fast clustering with lower bounds: No customer too far no shop too small. In submission. http:\/\/valis.cs.uiuc.edu\/~sariel\/papers\/12\/lbc\/ 2012.  A. Ene B. Raichel and S. Har-Peled. Fast clustering with lower bounds: No customer too far no shop too small. In submission. http:\/\/valis.cs.uiuc.edu\/~sariel\/papers\/12\/lbc\/ 2012."},{"key":"e_1_3_2_1_10_1","first-page":"85","volume-title":"Proc. 7th Canad. Conf. Comput. Geom.","author":"Erickson J.","year":"1995","unstructured":"J. Erickson .hrefhttp:\/\/compgeom.cs.uiuc.edu\/~jeffe\/pubs\/relative. htmlOn the relative complexities of some geometric problems . In Proc. 7th Canad. Conf. Comput. Geom. , pages 85 -- 90 , 1995 . J. Erickson.hrefhttp:\/\/compgeom.cs.uiuc.edu\/~jeffe\/pubs\/relative.htmlOn the relative complexities of some geometric problems. In Proc. 7th Canad. Conf. Comput. Geom., pages 85--90, 1995."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/0219013"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(85)90224-5"},{"key":"e_1_3_2_1_13_1","first-page":"3","article-title":"Simple randomized algorithms for closest pair problems","volume":"2","author":"Golin M.","year":"1995","unstructured":"M. Golin , R. Raman , C. Schwarz , and M. Smid . Simple randomized algorithms for closest pair problems . Nordic J. Comput. , 2 : 3 -- 27 , 1995 . M. Golin, R. Raman, C. Schwarz, and M. Smid. Simple randomized algorithms for closest pair problems. Nordic J. Comput., 2:3--27, 1995.","journal-title":"Nordic J. Comput."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/874063.875595"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-004-2822-7"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30538-5_27"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1064092.1064114"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007400"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-004-1123-0"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704446281"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1998196.1998269"},{"key":"e_1_3_2_1_22_1","volume-title":"Manuscript","author":"Har-Peled S.","year":"2012","unstructured":"S. Har-Peled and B. Raichel . hrefhttp:\/\/cs.uiuc.edu\/~sariel\/papers\/12\/aggregate\/Net and prune: A linear time algorithm for euclidean distance problems . Manuscript , 2012 . S. Har-Peled and B. Raichel.hrefhttp:\/\/cs.uiuc.edu\/~sariel\/papers\/12\/aggregate\/Net and prune: A linear time algorithm for euclidean distance problems. Manuscript, 2012."},{"key":"e_1_3_2_1_23_1","first-page":"798","volume-title":"Proc. 15th ACM-SIAM Sympos. Discrete Algorithms","author":"Krauthgamer R.","year":"2004","unstructured":"R. Krauthgamer and J. R. Lee . Navigating nets: simple algorithms for proximity search . In Proc. 15th ACM-SIAM Sympos. Discrete Algorithms , pages 798 -- 807 . Society for Industrial and Applied Mathematics , 2004 . R. Krauthgamer and J. R. Lee. Navigating nets: simple algorithms for proximity search. In Proc. 15th ACM-SIAM Sympos. Discrete Algorithms, pages 798--807. Society for Industrial and Applied Mathematics, 2004."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02574017"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2157.322410"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2422.322418"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01940877"},{"key":"e_1_3_2_1_28_1","first-page":"21","volume-title":"Algorithms and Complexity: New Directions and Recent Results","author":"Rabin M. O.","year":"1976","unstructured":"M. O. Rabin . Probabilistic algorithms . In J. F. Traub, editor, Algorithms and Complexity: New Directions and Recent Results , pages 21 -- 39 . Academic Press , 1976 . M. O. Rabin. Probabilistic algorithms. In J. F. Traub, editor, Algorithms and Complexity: New Directions and Recent Results, pages 21--39. Academic Press, 1976."},{"key":"e_1_3_2_1_29_1","first-page":"683","volume-title":"J. E. Goodman and J. O'Rourke","author":"Salowe J.","year":"1997","unstructured":"J. Salowe . Parametric search. In J. E. Goodman and J. O'Rourke , editors, Handbook of Discrete and Computational Geometry, chapter~37, pages 683 -- 698 . CRC Press LLC , Boca Raton, FL, 1997 . J. Salowe. Parametric search. In J. E. Goodman and J. O'Rourke, editors, Handbook of Discrete and Computational Geometry, chapter~37, pages 683--698. CRC Press LLC, Boca Raton, FL, 1997."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/646233.682381"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/B978-044482537-7\/50021-8"},{"key":"e_1_3_2_1_32_1","series-title":"Lect","first-page":"569","volume-title":"Proc. 9th Sympos. Theoret. Aspects Comput. Sci.","author":"Sharir M.","year":"1992","unstructured":"M. Sharir and E. Welzl . A combinatorial bound for linear programming and related problems . In Proc. 9th Sympos. Theoret. Aspects Comput. Sci. , volume 577 of Lect . Notes in Comp. Sci., pages 569 -- 579 . Springer-Verlag , 1992 . M. Sharir and E. Welzl. A combinatorial bound for linear programming and related problems. In Proc. 9th Sympos. Theoret. Aspects Comput. Sci., volume 577 of Lect. Notes in Comp. Sci., pages 569--579. Springer-Verlag, 1992."},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2004.03.006"}],"event":{"name":"STOC'13: Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Palo Alto California USA","acronym":"STOC'13"},"container-title":["Proceedings of the forty-fifth annual ACM symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2488608.2488684","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2488608.2488684","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:39:20Z","timestamp":1750235960000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2488608.2488684"}},"subtitle":["a linear time algorithm for euclidean distance problems"],"short-title":[],"issued":{"date-parts":[[2013,6]]},"references-count":33,"alternative-id":["10.1145\/2488608.2488684","10.1145\/2488608"],"URL":"https:\/\/doi.org\/10.1145\/2488608.2488684","relation":{},"subject":[],"published":{"date-parts":[[2013,6]]},"assertion":[{"value":"2013-06-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}