{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,7]],"date-time":"2026-07-07T00:07:51Z","timestamp":1783382871524,"version":"3.54.6"},"publisher-location":"Singapore","reference-count":15,"publisher":"Springer Nature Singapore","isbn-type":[{"value":"9789819610921","type":"print"},{"value":"9789819610938","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025]]},"DOI":"10.1007\/978-981-96-1093-8_39","type":"book-chapter","created":{"date-parts":[[2025,2,19]],"date-time":"2025-02-19T21:18:46Z","timestamp":1739999926000},"page":"478-489","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["The Voronoi Diagram of\u00a0Weakly Smooth Planar Point Sets in\u00a0$$O(\\log n)$$ Deterministic Rounds on\u00a0the\u00a0Congested Clique"],"prefix":"10.1007","author":[{"given":"Jesper","family":"Jansson","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Christos","family":"Levcopoulos","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andrzej","family":"Lingas","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Quan","family":"Xue","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2025,2,20]]},"reference":[{"key":"39_CR1","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1007\/BF01762120","volume":"3","author":"A Aggarwal","year":"1988","unstructured":"Aggarwal, A., Chazelle, B., Guibas, L.J., \u00d3\u2019D\u00fanlaing, C., Yap, C.-K.: Parallel computational geometry. Algorithmica 3, 293\u2013327 (1988)","journal-title":"Algorithmica"},{"issue":"2","key":"39_CR2","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1007\/BF01293667","volume":"14","author":"M Amato","year":"1995","unstructured":"Amato, M., Preparata, F.: A time-optimal parallel algorithm for three-dimensional convex hull. Algorithmica 14(2), 169\u2013182 (1995)","journal-title":"Algorithmica"},{"issue":"6","key":"39_CR3","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1007\/s00446-016-0270-2","volume":"32","author":"K Censor-Hillel","year":"2019","unstructured":"Censor-Hillel, K., Kaski, P., Korhonen, J.H., Lenzen, C., Paz, A., Suomela, J.: Algebraic methods in the congested clique. Distrib. Comput. 32(6), 461\u2013478 (2019)","journal-title":"Distrib. Comput."},{"key":"39_CR4","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1016\/j.jpdc.2023.02.010","volume":"177","author":"F Frei","year":"2023","unstructured":"Frei, F., Wada, K.: Efficient deterministic MapReduce algorithms for parallelizable problems. J. Parallel Distrib. Comput. 177, 28\u201338 (2023)","journal-title":"J. Parallel Distrib. Comput."},{"key":"39_CR5","unstructured":"Goodrich, M.: Randomized fully-scalable BSP techniques for multi-searching and convex hull construction. In: Proceedings of the Eighth Annual Symposium on Discrete Algorithms (SODA 1997), pp. 767\u2013776. ACM-SIAM (1997)"},{"key":"39_CR6","doi-asserted-by":"crossref","unstructured":"Jansson, J.,\u00a0Levcopoulos, C.,\u00a0Lingas, A.,\u00a0Polishchuk, V.: Convex hulls, triangulations, and Voronoi diagrams of planar point sets on the congested clique. arXiv:2305.09987 (2023). Preliminary version in Proceedings of the Thirty-Fifth Canadian Conference on Computational Geometry (CCCG\u00a02023), pp.\u00a0183\u2013189 (2023)","DOI":"10.2139\/ssrn.4654991"},{"key":"39_CR7","doi-asserted-by":"crossref","unstructured":"Lenzen, C.: Optimal deterministic routing and sorting on the congested clique. In: Proceedings of the 2013 ACM Symposium on Principles of Distributed Computing (PODC\u00a02013), pp. 42\u201350. ACM (2013)","DOI":"10.1145\/2484239.2501983"},{"key":"39_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"190","DOI":"10.1007\/3-540-19487-8_21","volume-title":"SWAT 88","author":"C Levcopoulos","year":"1988","unstructured":"Levcopoulos, C., Katajainen, J., Lingas, A.: An optimal expected-time parallel algorithm for Voronoi diagrams. In: Karlsson, R., Lingas, A. (eds.) SWAT 1988. LNCS, vol. 318, pp. 190\u2013198. Springer, Heidelberg (1988). https:\/\/doi.org\/10.1007\/3-540-19487-8_21"},{"issue":"1","key":"39_CR9","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1137\/S0097539704441848","volume":"35","author":"Z Lotker","year":"2005","unstructured":"Lotker, Z., Patt-Shamir, B., Pavlov, E., Peleg, D.: Minimum-weight spanning tree construction in $$O(\\log \\log n)$$ communication rounds. SIAM J. Comput. 35(1), 120\u2013131 (2005)","journal-title":"SIAM J. Comput."},{"key":"39_CR10","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1007\/s00446-021-00418-2","volume":"35","author":"D Nanongkai","year":"2022","unstructured":"Nanongkai, D., Scquizzato, M.: Equivalence classes and conditional hardness in massively parallel computing. Distrib. Comput. 35, 165\u2013183 (2022)","journal-title":"Distrib. Comput."},{"key":"39_CR11","doi-asserted-by":"crossref","unstructured":"Nowicki, K.: A deterministic algorithm for the MST problem in constant rounds of congested clique. In: Proceedings of the Fifty-Third Annual ACM SIGACT Symposium on Theory of Computing (STOC\u00a02021), pp. 1154\u20131165. ACM (2021)","DOI":"10.1145\/3406325.3451136"},{"key":"39_CR12","unstructured":"Pemmaraju, S.,\u00a0Sardeshmukh, V.: Super-fast MST algorithms in the congested clique using o(m) messages. In: Proceedings of the 36th Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016), pp. 47:1\u201347:15. LIPICS (2016)"},{"key":"39_CR13","doi-asserted-by":"publisher","unstructured":"Preparata, F.,\u00a0Shamos, M.: Computational Geometry: An Introduction, vol.\u00a010. In: Texts and Monographs in Computer Science. Springer-Verlag (1985). https:\/\/doi.org\/10.1007\/978-1-4612-1098-6","DOI":"10.1007\/978-1-4612-1098-6"},{"key":"39_CR14","doi-asserted-by":"crossref","unstructured":"Robinson, P.: Brief announcement: what can we compute in a single round of the congested clique? In: Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing (PODC\u00a02023), pp. 168\u2013171. ACM (2023)","DOI":"10.1145\/3583668.3594575"},{"key":"39_CR15","doi-asserted-by":"crossref","unstructured":"Vemuri, B.C.,\u00a0Varadarajan, R.,\u00a0Mayya, N.: An efficient expected time parallel algorithm for Voronoi construction. In: Proceedings of the Fourth Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA\u00a01992), pp. 392\u2013401. ACM (1992)","DOI":"10.1145\/140901.141924"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-981-96-1093-8_39","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,19]],"date-time":"2025-02-19T21:18:52Z","timestamp":1739999932000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-981-96-1093-8_39"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9789819610921","9789819610938"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-981-96-1093-8_39","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"20 February 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"COCOON","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Computing and Combinatorics Conference","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Shanghai","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"China","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23 August 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"25 August 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"30","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cocoon2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/anl.sjtu.edu.cn\/cocoon2024\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}