{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,9]],"date-time":"2026-01-09T20:03:45Z","timestamp":1767989025402,"version":"3.49.0"},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2015,12,10]],"date-time":"2015-12-10T00:00:00Z","timestamp":1449705600000},"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":["J. ACM"],"published-print":{"date-parts":[[2015,12,10]]},"abstract":"<jats:p>\n            We provide a general framework for getting expected linear time constant factor approximations (and in many cases FPTAS's) to several well known problems in Computational Geometry, such as\n            <jats:italic>k<\/jats:italic>\n            -center clustering and farthest nearest neighbor. The new approach is robust to variations in the input problem, and yet it is simple, elegant, and practical. In particular, many of these well studied problems which fit easily into our framework, either previously had no linear time approximation algorithm, or required rather involved algorithms and analysis. A short list of the problems we consider include farthest nearest neighbor,\n            <jats:italic>k<\/jats:italic>\n            -center clustering, smallest disk enclosing\n            <jats:italic>k<\/jats:italic>\n            points,\n            <jats:italic>k<\/jats:italic>\n            th largest distance,\n            <jats:italic>k<\/jats:italic>\n            th smallest\n            <jats:italic>m<\/jats:italic>\n            -nearest neighbor distance,\n            <jats:italic>k<\/jats:italic>\n            th heaviest edge in the MST and other spanning forest type problems, problems involving upward closed set systems, and more. Finally, we show how to extend our framework such that the linear running time bound holds with high probability.\n          <\/jats:p>","DOI":"10.1145\/2831230","type":"journal-article","created":{"date-parts":[[2015,12,14]],"date-time":"2015-12-14T14:19:41Z","timestamp":1450102781000},"page":"1-35","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":13,"title":["Net and Prune"],"prefix":"10.1145","volume":"62","author":[{"given":"Sariel","family":"Har-Peled","sequence":"first","affiliation":[{"name":"University of Illinois, Urbana-Champaign, Urbana, IL"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Benjamin","family":"Raichel","sequence":"additional","affiliation":[{"name":"University of Texas at Dallas, Richardson, TX"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2015,12,10]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"P. K. Agarwal S. Har-Peled and K. Varadarajan. 2005. Geometric approximation via coresets. In Combinatorial and Computational Geometry J. E. Goodman J. Pach and E. Welzl (Eds.). Cambridge New York.  P. K. Agarwal S. Har-Peled and K. Varadarajan. 2005. Geometric approximation via coresets. In Combinatorial and Computational Geometry J. E. Goodman J. Pach and E. Welzl (Eds.). Cambridge New York."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1008731.1008736"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1994.1038"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1798596.1798602"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/060669474"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0114-7"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/200836.200853"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2008.02.008"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1983.16"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/73393.73394"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187740"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-012-9402-z"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8655(93)90141-Y"},{"key":"e_1_2_1_14_1","unstructured":"A. Ene B. Raichel and S. Har-Peled. 2012. Fast clustering with lower bounds: No customer too far no shop too small. In submission. http:\/\/sarielhp.org\/papers\/12\/lbc\/.  A. Ene B. Raichel and S. Har-Peled. 2012. Fast clustering with lower bounds: No customer too far no shop too small. In submission. http:\/\/sarielhp.org\/papers\/12\/lbc\/."},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 7th Canadian Conference on Computer Geometry","author":"Erickson J.","year":"1995","unstructured":"J. Erickson . 1995 . On the relative complexities of some geometric problems . In Proceedings of the 7th Canadian Conference on Computer Geometry . Carleton University, Ottawa, Canada, 85--90. http:\/\/compgeom.cs.uiuc.edu\/&sim;jeffe\/pubs\/relative.html. J. Erickson. 1995. On the relative complexities of some geometric problems. In Proceedings of the 7th Canadian Conference on Computer Geometry. Carleton University, Ottawa, Canada, 85--90. http:\/\/compgeom.cs.uiuc.edu\/&sim;jeffe\/pubs\/relative.html."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/0213002"},{"key":"e_1_2_1_17_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 . 1995 . Simple randomized algorithms for closest pair problems . Nordic J. Comput. 2 (1995), 3 -- 27 . M. Golin, R. Raman, C. Schwarz, and M. Smid. 1995. Simple randomized algorithms for closest pair problems. Nordic J. Comput. 2 (1995), 3--27.","journal-title":"Nordic J. Comput."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(85)90224-5"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/874063.875595"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-004-2822-7"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30538-5_27"},{"key":"e_1_2_1_22_1","volume-title":"Geometric Approximation Algorithms. Mathematical Surveys and Monographs","author":"Har-Peled S.","unstructured":"S. Har-Peled . 2011. Geometric Approximation Algorithms. Mathematical Surveys and Monographs , Vol. 173 . Amer. Math. Soc., Boston, MA, USA. S. Har-Peled. 2011. Geometric Approximation Algorithms. Mathematical Surveys and Monographs, Vol. 173. Amer. Math. Soc., Boston, MA, USA."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-006-1271-x"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007400"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-004-1123-0"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704446281"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1998196.1998269"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488684"},{"key":"e_1_2_1_29_1","unstructured":"S. Har-Peled and B. Raichel. 2014. Net and Prune: A linear time algorithm for Euclidean distance problems. CoRR abs\/1409.7425 (2014). http:\/\/arxiv.org\/abs\/1409.7425.  S. Har-Peled and B. Raichel. 2014. Net and Prune: A linear time algorithm for Euclidean distance problems. CoRR abs\/1409.7425 (2014). http:\/\/arxiv.org\/abs\/1409.7425."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1995.1049"},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of SODA. Society for Industrial and Applied Mathematics","author":"Krauthgamer R.","unstructured":"R. Krauthgamer and J. R. Lee . 2004. Navigating nets: Simple algorithms for proximity search . In Proceedings of SODA. Society for Industrial and Applied Mathematics , Philadelphia, PA, 798--807. R. Krauthgamer and J. R. Lee. 2004. Navigating nets: Simple algorithms for proximity search. In Proceedings of SODA. Society for Industrial and Applied Mathematics, Philadelphia, PA, 798--807."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02574017"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01940877"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2157.322410"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2422.322418"},{"key":"e_1_2_1_36_1","unstructured":"R. Motwani and P. Raghavan. 1995. Randomized Algorithms. Cambridge University Press Cambridge UK. http:\/\/us.cambridge.org\/titles\/catalogue.asp?isbn=0521474655.   R. Motwani and P. Raghavan. 1995. Randomized Algorithms. Cambridge University Press Cambridge UK. http:\/\/us.cambridge.org\/titles\/catalogue.asp?isbn=0521474655."},{"key":"e_1_2_1_37_1","volume-title":"Computational Geometry: An Introduction Through Randomized Algorithms","author":"Mulmuley K.","year":"1994","unstructured":"K. Mulmuley . 1994 . Computational Geometry: An Introduction Through Randomized Algorithms . Prentice Hall, Englewood Cliffs , NJ. K. Mulmuley. 1994. Computational Geometry: An Introduction Through Randomized Algorithms. Prentice Hall, Englewood Cliffs, NJ."},{"key":"e_1_2_1_38_1","volume-title":"Algorithms and Complexity: New Directions and Recent Results","author":"Rabin M. O.","unstructured":"M. O. Rabin . 1976. Probabilistic algorithms . In Algorithms and Complexity: New Directions and Recent Results , J. F. Traub (Ed.). Academic Press , Orlando, FL, USA , 21--39. M. O. Rabin. 1976. Probabilistic algorithms. In Algorithms and Complexity: New Directions and Recent Results, J. F. Traub (Ed.). Academic Press, Orlando, FL, USA, 21--39."},{"key":"e_1_2_1_39_1","volume-title":"Handbook of Discrete and Computational Geometry, J. E. Goodman and J. O'Rourke (Eds.)","author":"Salowe J.","unstructured":"J. Salowe . 1997. Parametric search . In Handbook of Discrete and Computational Geometry, J. E. Goodman and J. O'Rourke (Eds.) . CRC Press LLC , Boca Raton, FL , Chapter 37, 683--698. J. Salowe. 1997. Parametric search. In Handbook of Discrete and Computational Geometry, J. E. Goodman and J. O'Rourke (Eds.). CRC Press LLC, Boca Raton, FL, Chapter 37, 683--698."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.5555\/646233.682381"},{"key":"e_1_2_1_41_1","doi-asserted-by":"crossref","unstructured":"M.\n      Sharir\n     and \n      E.\n      Welzl\n  . \n  1992\n  . A combinatorial bound for linear programming and related problems. In Proceedings of the 9th Symposium on Theoretical Aspects of Computer Science Lecture Notes in Computer Science vol. \n  577\n  . \n  Springer 569--579.   M. Sharir and E. Welzl. 1992. A combinatorial bound for linear programming and related problems. In Proceedings of the 9th Symposium on Theoretical Aspects of Computer Science Lecture Notes in Computer Science vol. 577. Springer 569--579.","DOI":"10.1007\/3-540-55210-3_213"},{"key":"e_1_2_1_42_1","volume-title":"Handbook of Computational Geometry, J.-R","author":"Smid M.","unstructured":"M. Smid . 2000. Closest-point problems in computational geometry . In Handbook of Computational Geometry, J.-R . Sack and J. Urrutia (Eds.). Elsevier , Amsterdam, Netherlands , 877--935. M. Smid. 2000. Closest-point problems in computational geometry. In Handbook of Computational Geometry, J.-R. Sack and J. Urrutia (Eds.). Elsevier, Amsterdam, Netherlands, 877--935."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2004.03.006"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2831230","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2831230","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T05:48:12Z","timestamp":1750225692000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2831230"}},"subtitle":["A Linear Time Algorithm for Euclidean Distance Problems"],"short-title":[],"issued":{"date-parts":[[2015,12,10]]},"references-count":43,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2015,12,10]]}},"alternative-id":["10.1145\/2831230"],"URL":"https:\/\/doi.org\/10.1145\/2831230","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,12,10]]},"assertion":[{"value":"2013-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-12-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}