{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,24]],"date-time":"2025-10-24T16:42:48Z","timestamp":1761324168037,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":54,"publisher":"ACM","license":[{"start":{"date-parts":[[2018,7,11]],"date-time":"2018-07-11T00:00:00Z","timestamp":1531267200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1533858"],"award-info":[{"award-number":["CCF-1533858"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2018,7,11]]},"DOI":"10.1145\/3210377.3210380","type":"proceedings-article","created":{"date-parts":[[2018,7,12]],"date-time":"2018-07-12T17:46:44Z","timestamp":1531417604000},"page":"235-246","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":13,"title":["Parallel Write-Efficient Algorithms and Data Structures for Computational Geometry"],"prefix":"10.1145","author":[{"given":"Guy E.","family":"Blelloch","sequence":"first","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA, USA"}]},{"given":"Yan","family":"Gu","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA, USA"}]},{"given":"Julian","family":"Shun","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, MA, USA"}]},{"given":"Yihan","family":"Sun","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA, USA"}]}],"member":"320","published-online":{"date-parts":[[2018,7,11]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/48529.48535"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/1882123.1882133"},{"key":"e_1_3_2_1_3_1","volume-title":"Real-time rendering","author":"Akenine-M\u00f6ller T.","year":"2008","unstructured":"T. Akenine-M\u00f6ller , E. Haines , and N. Hoffman . Real-time rendering . CRC Press , 2008 . T. Akenine-M\u00f6ller, E. Haines, and N. Hoffman. Real-time rendering. CRC Press, 2008."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/303976.304010"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753970240481X"},{"key":"e_1_3_2_1_6_1","first-page":"497","volume-title":"Synthesis of Parallel Algorithms","author":"Atallah M.","year":"1993","unstructured":"M. Atallah and M. Goodrich . Deterministic parallel computational geometry . In Synthesis of Parallel Algorithms , pages 497 -- 536 . Morgan Kaufmann , 1993 . M. Atallah and M. Goodrich. Deterministic parallel computational geometry. In Synthesis of Parallel Algorithms, pages 497--536. Morgan Kaufmann, 1993."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/11841036_12"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2935764.2935767"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/361002.361007"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(79)90117-0"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63478"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2935764.2935768"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2755573.2755604"},{"key":"e_1_3_2_1_14_1","volume-title":"ESA","author":"Blelloch G. E.","year":"2016","unstructured":"G. E. Blelloch , J. T. Fineman , P. B. Gibbons , Y. Gu , and J. Shun . Efficient algorithms with asymmetric read and write costs . In ESA , 2016 . G. E. Blelloch, J. T. Fineman, P. B. Gibbons, Y. Gu, and J. Shun. Efficient algorithms with asymmetric read and write costs. In ESA, 2016."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2935764.2935766"},{"key":"e_1_3_2_1_16_1","volume-title":"Parallel write-efficient algorithms and data structures for computational geometry. arXiv preprint:1805.05592","author":"Blelloch G. E.","year":"2018","unstructured":"G. E. Blelloch , Y. Gu , J. Shun , and Y. Sun . Parallel write-efficient algorithms and data structures for computational geometry. arXiv preprint:1805.05592 , 2018 . G. E. Blelloch, Y. Gu, J. Shun, and Y. Sun. Parallel write-efficient algorithms and data structures for computational geometry. arXiv preprint:1805.05592, 2018."},{"key":"e_1_3_2_1_17_1","volume-title":"Design and implementation of a practical parallel Delaunay algorithm. Algorithmica, 24(3--4)","author":"Blelloch G. E.","year":"1999","unstructured":"G. E. Blelloch , J. C. Hardwick , G. L. Miller , and D. Talmor . Design and implementation of a practical parallel Delaunay algorithm. Algorithmica, 24(3--4) , 1999 . G. E. Blelloch, J. C. Hardwick, G. L. Miller, and D. Talmor. Design and implementation of a practical parallel Delaunay algorithm. Algorithmica, 24(3--4), 1999."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(93)90024-N"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2016.114"},{"key":"e_1_3_2_1_20_1","volume-title":"CIDR","author":"Chen S.","year":"2011","unstructured":"S. Chen , P. B. Gibbons , and S. Nath . Rethinking database algorithms for phase change memory . In CIDR , 2011 . S. Chen, P. B. Gibbons, and S. Nath. Rethinking database algorithms for phase change memory. In CIDR, 2011."},{"key":"e_1_3_2_1_21_1","volume-title":"II. Discrete & Computational Geometry, 4(5)","author":"Clarkson K. L.","year":"1989","unstructured":"K. L. Clarkson and P. W. Shor . Applications of random sampling in computational geometry , II. Discrete & Computational Geometry, 4(5) , 1989 . K. L. Clarkson and P. W. Shor. Applications of random sampling in computational geometry, II. Discrete & Computational Geometry, 4(5), 1989."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/0217049"},{"key":"e_1_3_2_1_23_1","volume-title":"Introduction to Algorithms","author":"Cormen T. H.","year":"2009","unstructured":"T. H. Cormen , C. E. Leiserson , R. L. Rivest , and C. Stein . Introduction to Algorithms ( 3 rd edition). MIT Press , 2009 . T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms (3rd edition). MIT Press, 2009.","edition":"3"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/1370949"},{"key":"e_1_3_2_1_25_1","volume-title":"Dynamic data structures for orthogonal intersection queries. Technische Universit\u00e4t Graz\/Forschungszentrum Graz","author":"Edelsbrunner H.","year":"1980","unstructured":"H. Edelsbrunner . Dynamic data structures for orthogonal intersection queries. Technische Universit\u00e4t Graz\/Forschungszentrum Graz . Institut f\u00fcr Informationsverarbeitung , 1980 . H. Edelsbrunner. Dynamic data structures for orthogonal intersection queries. Technische Universit\u00e4t Graz\/Forschungszentrum Graz. Institut f\u00fcr Informationsverarbeitung, 1980."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-07959-2_14"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1089733.1089735"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(87)90002-0"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2492045.2492054"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2755573.2755597"},{"issue":"4","key":"e_1_3_2_1_31_1","first-page":"381","volume":"7","author":"Guibas L. J.","year":"1992","unstructured":"L. J. Guibas , D. E. Knuth , and M. Sharir . Randomized incremental construction of Delaunay and Voronoi diagrams. Algorithmica , 7 ( 4 ): 381 -- 413 , 1992 . L. J. Guibas, D. E. Knuth, and M. Sharir. Randomized incremental construction of Delaunay and Voronoi diagrams. Algorithmica, 7(4):381--413, 1992.","journal-title":"Randomized incremental construction of Delaunay and Voronoi diagrams. Algorithmica"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/971697.602266"},{"key":"e_1_3_2_1_33_1","volume-title":"Geometric approximation algorithms","author":"Har-Peled S.","year":"2011","unstructured":"S. Har-Peled . Geometric approximation algorithms , volume 173 . American Mathematical Society , 2011 . S. Har-Peled. Geometric approximation algorithms, volume 173. American Mathematical Society, 2011."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3087556.3087583"},{"key":"e_1_3_2_1_35_1","volume-title":"Introduction to Parallel Algorithms","author":"JaJa J.","year":"1992","unstructured":"J. JaJa . Introduction to Parallel Algorithms . Addison-Wesley Professional , 1992 . J. JaJa. Introduction to Parallel Algorithms. Addison-Wesley Professional, 1992."},{"key":"e_1_3_2_1_36_1","volume-title":"R-trees: Theory and Applications","author":"Manolopoulos Y.","year":"2010","unstructured":"Y. Manolopoulos , A. Nanopoulos , A. N. Papadopoulos , and Y. Theodoridis . R-trees: Theory and Applications . Springer Science & Business Media , 2010 . Y. Manolopoulos, A. Nanopoulos, A. N. Papadopoulos, and Y. Theodoridis. R-trees: Theory and Applications. Springer Science & Business Media, 2010."},{"key":"e_1_3_2_1_37_1","volume-title":"Efficient algorithms for enumerating intersecting intervals and rectangles. Technical report","author":"McCreight E. M.","year":"1980","unstructured":"E. M. McCreight . Efficient algorithms for enumerating intersecting intervals and rectangles. Technical report , 1980 . E. M. McCreight. Efficient algorithms for enumerating intersecting intervals and rectangles. Technical report, 1980."},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214021"},{"key":"e_1_3_2_1_39_1","volume-title":"Computational geometry--an introduction through randomized algorithms","author":"Mulmuley K.","year":"1994","unstructured":"K. Mulmuley . Computational geometry--an introduction through randomized algorithms . Prentice Hall , 1994 . K. Mulmuley. Computational geometry--an introduction through randomized algorithms. Prentice Hall, 1994."},{"key":"e_1_3_2_1_40_1","series-title":"SIAM journal on Computing, 2(1)","volume-title":"Binary search trees of bounded balance","author":"Nievergelt J.","year":"1973","unstructured":"J. Nievergelt and E. M. Reingold . Binary search trees of bounded balance . SIAM journal on Computing, 2(1) , 1973 . J. Nievergelt and E. M. Reingold. Binary search trees of bounded balance. SIAM journal on Computing, 2(1), 1973."},{"key":"e_1_3_2_1_41_1","volume-title":"The design of dynamic data structures","author":"Overmars M. H.","year":"1983","unstructured":"M. H. Overmars . The design of dynamic data structures , volume 156 . Springer Science & Business Media , 1983 . M. H. Overmars. The design of dynamic data structures, volume 156. Springer Science & Business Media, 1983."},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jss.2009.02.028"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1137\/0218041"},{"key":"e_1_3_2_1_44_1","volume-title":"Optimal randomized parallel algorithms for computational geometry. Algorithmica, 7(1--6):91--117","author":"Reif J. H.","year":"1992","unstructured":"J. H. Reif and S. Sen . Optimal randomized parallel algorithms for computational geometry. Algorithmica, 7(1--6):91--117 , 1992 . J. H. Reif and S. Sen. Optimal randomized parallel algorithms for computational geometry. Algorithmica, 7(1--6):91--117, 1992."},{"key":"e_1_3_2_1_45_1","volume-title":"New Trends in Discrete and Computational Geometry.","author":"Seidel R.","year":"1993","unstructured":"R. Seidel . Backwards analysis of randomized geometric algorithms . In New Trends in Discrete and Computational Geometry. 1993 . R. Seidel. Backwards analysis of randomized geometric algorithms. In New Trends in Discrete and Computational Geometry. 1993."},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.5555\/2722129.2722159"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/2367574.2367578"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/2312005.2312046"},{"key":"e_1_3_2_1_49_1","volume-title":"Parallel range and segment queries with augmented maps. arXiv preprint:1803.08621","author":"Sun Y.","year":"2018","unstructured":"Y. Sun and G. E. Blelloch . Parallel range and segment queries with augmented maps. arXiv preprint:1803.08621 , 2018 . Y. Sun and G. E. Blelloch. Parallel range and segment queries with augmented maps. arXiv preprint:1803.08621, 2018."},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/3178487.3178509"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(83)90099-6"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33074-2_30"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732269.2732277"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/1189762.1206075"}],"event":{"name":"SPAA '18: 30th ACM Symposium on Parallelism in Algorithms and Architectures","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory","SIGARCH ACM Special Interest Group on Computer Architecture","EATCS European Association for Theoretical Computer Science"],"location":"Vienna Austria","acronym":"SPAA '18"},"container-title":["Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3210377.3210380","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3210377.3210380","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3210377.3210380","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:08:13Z","timestamp":1750208893000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3210377.3210380"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,7,11]]},"references-count":54,"alternative-id":["10.1145\/3210377.3210380","10.1145\/3210377"],"URL":"https:\/\/doi.org\/10.1145\/3210377.3210380","relation":{},"subject":[],"published":{"date-parts":[[2018,7,11]]},"assertion":[{"value":"2018-07-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}