{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,10]],"date-time":"2023-01-10T08:28:12Z","timestamp":1673339292770},"reference-count":81,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2020,9,19]],"date-time":"2020-09-19T00:00:00Z","timestamp":1600473600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["CCF-1314590 and CCF-1533858"]},{"name":"Miller Institute for Basic Research in Science at UC Berkeley"},{"name":"Intel Science and Technology Center for Cloud Computing"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2020,10,31]]},"abstract":"In this article, we show that many sequential randomized incremental algorithms are in fact parallel. We consider algorithms for several problems, including Delaunay triangulation, linear programming, closest pair, smallest enclosing disk, least-element lists, and strongly connected components.<\/jats:p>\n We analyze the dependencies between iterations in an algorithm and show that the dependence structure is shallow with high probability or that, by violating some dependencies, the structure is shallow and the work is not increased significantly. We identify three types of algorithms based on their dependencies and present a framework for analyzing each type. Using the framework gives work-efficient polylogarithmic-depth parallel algorithms for most of the problems that we study.<\/jats:p>\n This article shows the first incremental Delaunay triangulation algorithm with optimal work and polylogarithmic depth. This result is important, since most implementations of parallel Delaunay triangulation use the incremental approach. Our results also improve bounds on strongly connected components and least-element lists and significantly simplify parallel algorithms for several problems.<\/jats:p>","DOI":"10.1145\/3402819","type":"journal-article","created":{"date-parts":[[2020,9,19]],"date-time":"2020-09-19T16:06:09Z","timestamp":1600531569000},"page":"1-27","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Parallelism in Randomized Incremental Algorithms"],"prefix":"10.1145","volume":"67","author":[{"given":"Guy E.","family":"Blelloch","sequence":"first","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA"}]},{"given":"Yan","family":"Gu","sequence":"additional","affiliation":[{"name":"University of California, Riverside, CA"}]},{"given":"Julian","family":"Shun","sequence":"additional","affiliation":[{"name":"MIT CSAIL, Cambridge, MA"}]},{"given":"Yihan","family":"Sun","sequence":"additional","affiliation":[{"name":"University of California, Riverside, CA"}]}],"member":"320","published-online":{"date-parts":[[2020,9,19]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/129712.129744"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3212734.3212756"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3323165.3323201"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/174652.174661"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the Symposium on Foundations of Computer Science (FOCS\u201994)","author":"Amato Nancy M.","unstructured":"Nancy M. Amato , Michael T. Goodrich , and Edgar A. Ramos . 1994. Parallel algorithms for higher-dimensional convex hulls . In Proceedings of the Symposium on Foundations of Computer Science (FOCS\u201994) . 683--694. Nancy M. Amato, Michael T. Goodrich, and Edgar A. Ramos. 1994. Parallel algorithms for higher-dimensional convex hulls. In Proceedings of the Symposium on Foundations of Computer Science (FOCS\u201994). 683--694."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2011.59"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2935764.2935767"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1137856.1137900"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2755573.2755604"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the European Symposium on Algorithms (ESA\u201916)","author":"Blelloch Guy E.","year":"2016","unstructured":"Guy E. Blelloch , Jeremy T. Fineman , Phillip B. Gibbons , Yan Gu , and Julian Shun . 2016 . Efficient algorithms with asymmetric read and write costs . In Proceedings of the European Symposium on Algorithms (ESA\u201916) . Guy E. Blelloch, Jeremy T. Fineman, Phillip B. Gibbons, Yan Gu, and Julian Shun. 2016. Efficient algorithms with asymmetric read and write costs. In Proceedings of the European Symposium on Algorithms (ESA\u201916)."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2145816.2145840"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2312005.2312058"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2935764.2935766"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3210377.3210380"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3350755.3400255"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP\u201917)","author":"Blelloch Guy E.","year":"2017","unstructured":"Guy E. Blelloch , Yan Gu , and Yihan Sun . 2017 . Efficient construction of probabilistic tree embeddings . In Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP\u201917) . Guy E. Blelloch, Yan Gu, and Yihan Sun. 2017. Efficient construction of probabilistic tree embeddings. In Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP\u201917)."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2935764.2935765"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2312005.2312045"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00008262"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the Usenix Conference on Hot Topics in Parallelism (HotPar\u201909)","author":"Bocchino Robert L.","year":"2009","unstructured":"Robert L. Bocchino , Vikram S. Adve , Sarita V. Adve , and Marc Snir . 2009 . Parallel programming must be deterministic by default . In Proceedings of the Usenix Conference on Hot Topics in Parallelism (HotPar\u201909) . Robert L. Bocchino, Vikram S. Adve, Sarita V. Adve, and Marc Snir. 2009. Parallel programming must be deterministic by default. In Proceedings of the Usenix Conference on Hot Topics in Parallelism (HotPar\u201909)."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(93)90024-N"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/321812.321815"},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the IEEE International Symposium on Workload Characterization (IISWC\u201908)","author":"Minh Chi Cao","year":"2008","unstructured":"Chi Cao Minh , JaeWoong Chung , Christos Kozyrakis , and Kunle Olukotun . 2008 . STAMP: Stanford transactional applications for multi-processing . In Proceedings of the IEEE International Symposium on Workload Characterization (IISWC\u201908) . Chi Cao Minh, JaeWoong Chung, Christos Kozyrakis, and Kunle Olukotun. 2008. STAMP: Stanford transactional applications for multi-processing. In Proceedings of the IEEE International Symposium on Workload Characterization (IISWC\u201908)."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(01)00028-1"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1111\/1467-8659.1230129"},{"key":"e_1_2_1_26_1","volume-title":"International conference on computational science and its applications. In Speculative Parallelization of a Randomized Incremental Convex Hull Algorithm. 188--197","author":"Cintra Marcelo","year":"2004","unstructured":"Marcelo Cintra , Diego R. Llanos , and Bel\u00e9n Palop . 2004 . International conference on computational science and its applications. In Speculative Parallelization of a Randomized Incremental Convex Hull Algorithm. 188--197 . Marcelo Cintra, Diego R. Llanos, and Bel\u00e9n Palop. 2004. International conference on computational science and its applications. In Speculative Parallelization of a Randomized Incremental Convex Hull Algorithm. 188--197."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187740"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1534"},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA;04)","author":"Cohen Edith","year":"2004","unstructured":"Edith Cohen and Haim Kaplan . 2004 . Efficient estimation algorithms for neighborhood variance and other moments . In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA;04) . 157--166. Edith Cohen and Haim Kaplan. 2004. Efficient estimation algorithms for neighborhood variance and other moments. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA;04). 157--166."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/0217049"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01944352"},{"key":"e_1_2_1_33_1","volume-title":"Introduction to Algorithms","author":"Cormen Thomas H.","unstructured":"Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest , and Clifford Stein . 2009. Introduction to Algorithms ( 3 rd ed.). MIT Press . Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2009. Introduction to Algorithms (3rd ed.). MIT Press.","edition":"3"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77974-2"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(90)90026-T"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3210377.3210414"},{"key":"e_1_2_1_37_1","volume-title":"Proc. XV Jornadas de Paralelismo","author":"Diaz Pedro","year":"2004","unstructured":"Pedro Diaz , Diego R. Llanos , and Belen Palop . 2004 . Parallelizing 2D-convex hulls on clusters: Sorting matters . Proc. XV Jornadas de Paralelismo (2004), 247--252. Pedro Diaz, Diego R. Llanos, and Belen Palop. 2004. Parallelizing 2D-convex hulls on clusters: Sorting matters. Proc. XV Jornadas de Paralelismo (2004), 247--252."},{"key":"e_1_2_1_38_1","volume-title":"Proceedings of the Advances in Neural Information Processing Systems (NIPS\u201913)","author":"Du Nan","year":"2013","unstructured":"Nan Du , Le Song , Manuel Gomez-Rodriguez , and Hongyuan Zha . 2013 . Scalable influence estimation in continuous-time diffusion networks . In Proceedings of the Advances in Neural Information Processing Systems (NIPS\u201913) . 3147--3155. Nan Du, Le Song, Manuel Gomez-Rodriguez, and Hongyuan Zha. 2013. Scalable influence estimation in continuous-time diffusion networks. In Proceedings of the Advances in Neural Information Processing Systems (NIPS\u201913). 3147--3155."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/220279.220316"},{"key":"e_1_2_1_40_1","volume-title":"Geometry and Topology for Mesh Generation","author":"Edelsbrunner Herbert","unstructured":"Herbert Edelsbrunner . 2006. Geometry and Topology for Mesh Generation . Cambridge University Press . Herbert Edelsbrunner. 2006. Geometry and Topology for Mesh Generation. Cambridge University Press."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01975867"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.04.011"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188926"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1991.185438"},{"key":"e_1_2_1_45_1","first-page":"3","article-title":"Simple randomized algorithms for closest pair problems","volume":"2","author":"Golin Mordecai","year":"1995","unstructured":"Mordecai Golin , Rajeev Raman , Christian Schwarz , and Michiel Smid . 1995 . Simple randomized algorithms for closest pair problems . Nord. J. Comput. 2 , 1 (1995), 3 -- 27 . Mordecai Golin, Rajeev Raman, Christian Schwarz, and Michiel Smid. 1995. Simple randomized algorithms for closest pair problems. Nord. J. Comput. 2, 1 (1995), 3--27.","journal-title":"Nord. J. Comput."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.apm.2005.05.022"},{"key":"e_1_2_1_47_1","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA\u201996)","author":"Goodrich Michael T.","year":"1996","unstructured":"Michael T. Goodrich . 1996 . Fixed-dimensional parallel linear programming via relative \u03b5-approximations . In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA\u201996) . 132--141. Michael T. Goodrich. 1996. Fixed-dimensional parallel linear programming via relative \u03b5-approximations. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA\u201996). 132--141."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009325"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/21.2.168"},{"key":"e_1_2_1_50_1","volume-title":"Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA\u201915)","author":"Gu Yan","unstructured":"Yan Gu , Julian Shun , Yihan Sun , and Guy E. Blelloch . 2015. A top-down parallel semisort . In Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA\u201915) . 24--34. Yan Gu, Julian Shun, Yihan Sun, and Guy E. Blelloch. 2015. A top-down parallel semisort. In Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA\u201915). 24--34."},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01758770"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-54233-7_151"},{"key":"e_1_2_1_53_1","volume-title":"Geometric Approximation Algorithms","author":"Sariel","unstructured":"Sariel Har-peled. 2011. Geometric Approximation Algorithms . American Mathematical Society . Sariel Har-peled. 2011. Geometric Approximation Algorithms. American Mathematical Society."},{"key":"e_1_2_1_54_1","volume-title":"Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA\u201914)","author":"Hasenplaugh William","unstructured":"William Hasenplaugh , Tim Kaler , Tao B. Schardl , and Charles E. Leiserson . 2014. Ordering heuristics for parallel graph coloring . In Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA\u201914) . 166--177. William Hasenplaugh, Tim Kaler, Tao B. Schardl, and Charles E. Leiserson. 2014. Ordering heuristics for parallel graph coloring. In Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA\u201914). 166--177."},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/2503210.2503246"},{"key":"e_1_2_1_56_1","volume-title":"Introduction to Parallel Algorithms","author":"Jaja Joseph","unstructured":"Joseph Jaja . 1992. Introduction to Parallel Algorithms . Addison-Wesley Professional . Joseph Jaja. 1992. Introduction to Parallel Algorithms. Addison-Wesley Professional."},{"key":"e_1_2_1_57_1","volume-title":"C","author":"\u00a0al Svante Janson","year":"2018","unstructured":"Svante Janson et \u00a0al . 2018. Tail bounds for sums of geometric and exponential variables. Stat. Probab. Lett. 135 , C ( 2018 ), 1--6. Svante Janson et\u00a0al. 2018. Tail bounds for sums of geometric and exponential variables. Stat. Probab. Lett. 135, C (2018), 1--6."},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-012-0157-9"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1995.1049"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1997.0888"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICPPW.2005.49"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1137\/0212052"},{"key":"e_1_2_1_63_1","volume-title":"Computational Geometry\u2014An Introduction Through Randomized Algorithms","author":"Mulmuley Ketan","unstructured":"Ketan Mulmuley . 1994. Computational Geometry\u2014An Introduction Through Randomized Algorithms . Prentice Hall . Ketan Mulmuley. 1994. Computational Geometry\u2014An Introduction Through Randomized Algorithms. Prentice Hall."},{"key":"e_1_2_1_64_1","volume-title":"Proceedings of the Advances in Neural Information Processing Systems (NIPS\u201915)","author":"Pan Xinghao","unstructured":"Xinghao Pan , Dimitris Papailiopoulos , Samet Oymak , Benjamin Recht , Kannan Ramchandran , and Michael I. Jordan . 2015. Parallel correlation clustering on big graphs . In Proceedings of the Advances in Neural Information Processing Systems (NIPS\u201915) . Xinghao Pan, Dimitris Papailiopoulos, Samet Oymak, Benjamin Recht, Kannan Ramchandran, and Michael I. Jordan. 2015. Parallel correlation clustering on big graphs. In Proceedings of the Advances in Neural Information Processing Systems (NIPS\u201915)."},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993498.1993501"},{"key":"e_1_2_1_66_1","unstructured":"Michael O. Rabin. 1976. Probabilistic algorithms. Algorithms and Complexity: New Directions and Recent Results. 21--39. Michael O. Rabin. 1976. Probabilistic algorithms. Algorithms and Complexity: New Directions and Recent Results. 21--39."},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1137\/0218041"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(85)90024-9"},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1137\/0221031"},{"key":"e_1_2_1_70_1","volume-title":"Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA\u201908)","author":"Schudy Warren","year":"2008","unstructured":"Warren Schudy . 2008 . Finding strongly connected components in parallel using O(log2 n) reachability queries . In Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA\u201908) . 146--151. Warren Schudy. 2008. Finding strongly connected components in parallel using O(log2 n) reachability queries. In Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA\u201908). 146--151."},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.5555\/120885.120888"},{"key":"e_1_2_1_72_1","doi-asserted-by":"crossref","unstructured":"Raimund Seidel. 1993. Backwards analysis of randomized geometric algorithms. In New Trends in Discrete and Computational Geometry. 37--67. Raimund Seidel. 1993. Backwards analysis of randomized geometric algorithms. In New Trends in Discrete and Computational Geometry. 37--67.","DOI":"10.1007\/978-3-642-58043-7_3"},{"key":"e_1_2_1_73_1","volume-title":"Department of Computer Science","author":"Sen S.","unstructured":"S. Sen . 1995. A deterministic poly(log log n) time optimal CRCW PRAM algorithm for linear programming in fixed dimensions. Technical report , Department of Computer Science , University of Newcastle . S. Sen. 1995. A deterministic poly(log log n) time optimal CRCW PRAM algorithm for linear programming in fixed dimensions. Technical report, Department of Computer Science, University of Newcastle."},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1145\/2312005.2312018"},{"key":"e_1_2_1_75_1","volume-title":"Gibbons","author":"Shun Julian","year":"2015","unstructured":"Julian Shun , Yan Gu , Guy E. Blelloch , Jeremy T. Fineman , and Phillip B . Gibbons . 2015 . Sequential random permutation, list contraction and tree contraction are highly parallel. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA\u201915). 431--448. Julian Shun, Yan Gu, Guy E. Blelloch, Jeremy T. Fineman, and Phillip B. Gibbons. 2015. Sequential random permutation, list contraction and tree contraction are highly parallel. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA\u201915). 431--448."},{"key":"e_1_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2014.64"},{"key":"e_1_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.1145\/265910.265923"},{"key":"e_1_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.1137\/0201010"},{"key":"e_1_2_1_79_1","unstructured":"Daniel Tomkins Timmie Smith Nancy M. Amato and Lawrence Rauchwerger. 2015. Efficient reachability-based parallel algorithms for finding strongly connected components. Technical report Texas A8M University. Daniel Tomkins Timmie Smith Nancy M. Amato and Lawrence Rauchwerger. 2015. Efficient reachability-based parallel algorithms for finding strongly connected components. Technical report Texas A8M University."},{"key":"e_1_2_1_80_1","doi-asserted-by":"publisher","DOI":"10.1137\/0220006"},{"key":"e_1_2_1_81_1","volume-title":"Thinking in parallel: Some basic data-parallel algorithms and techniques","author":"Vishkin Uzi","year":"2010","unstructured":"Uzi Vishkin . 2010. Thinking in parallel: Some basic data-parallel algorithms and techniques , 2010 . Class notes from a course on parallel algorithms at UMD. Retrieved from http:\/\/users.umiacs.umd.edu\/~vishkin\/PUBLICATIONS\/classnotes.pdf. Uzi Vishkin. 2010. Thinking in parallel: Some basic data-parallel algorithms and techniques, 2010. Class notes from a course on parallel algorithms at UMD. Retrieved from http:\/\/users.umiacs.umd.edu\/~vishkin\/PUBLICATIONS\/classnotes.pdf."},{"key":"e_1_2_1_82_1","unstructured":"Emo Welzl. 1991. Smallest enclosing disks (balls and ellipsoids). In New Results and New Trends in Computer Science. Emo Welzl. 1991. Smallest enclosing disks (balls and ellipsoids). In New Results and New Trends in Computer Science."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3402819","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3402819","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T08:03:06Z","timestamp":1672560186000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3402819"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,9,19]]},"references-count":81,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2020,10,31]]}},"alternative-id":["10.1145\/3402819"],"URL":"http:\/\/dx.doi.org\/10.1145\/3402819","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":["Artificial Intelligence","Hardware and Architecture","Information Systems","Control and Systems Engineering","Software"],"published":{"date-parts":[[2020,9,19]]},"assertion":[{"value":"2018-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-09-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}