{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:46:32Z","timestamp":1740109592958,"version":"3.37.3"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2023,3,25]],"date-time":"2023-03-25T00:00:00Z","timestamp":1679702400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,3,25]],"date-time":"2023-03-25T00:00:00Z","timestamp":1679702400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001711","name":"Swiss National Science Foundation","doi-asserted-by":"crossref","award":["SNF-200021E-154387"],"award-info":[{"award-number":["SNF-200021E-154387"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2023,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Updating an abstract Voronoi diagram in linear time, after deletion of one site, has been an open problem in a long time; similarly, for any concrete Voronoi diagram of generalized (non-point) sites. In this paper we present a simple, expected linear-time algorithm to update an abstract Voronoi diagram after deletion of one site. To achieve this result, we use the concept of a Voronoi-like diagram, a relaxed Voronoi structure of independent interest. Voronoi-like diagrams serve as intermediate structures, which are considerably simpler to compute, thus, making an expected linear-time construction possible. We formalize the concept and prove that it is robust under insertion, therefore, enabling its use in incremental constructions. The time-complexity analysis introduces a variant to backwards analysis, which is applicable to order-dependent structures. We further extend the technique to compute in expected linear time: the order-<jats:inline-formula><jats:alternatives><jats:tex-math>$$(k\\,{+}\\,1)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>k<\/mml:mi>\n                    <mml:mspace\/>\n                    <mml:mo>+<\/mml:mo>\n                    <mml:mspace\/>\n                    <mml:mn>1<\/mml:mn>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> subdivision within an order-<jats:italic>k<\/jats:italic> Voronoi region, and the farthest abstract Voronoi diagram, after the order of its regions at infinity is known.<\/jats:p>","DOI":"10.1007\/s00454-022-00463-z","type":"journal-article","created":{"date-parts":[[2023,3,25]],"date-time":"2023-03-25T22:03:01Z","timestamp":1679781781000},"page":"1040-1078","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Deletion in Abstract Voronoi Diagrams in Expected Linear Time and Related Problems"],"prefix":"10.1007","volume":"69","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9741-2797","authenticated-orcid":false,"given":"Kolja","family":"Junginger","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0144-7384","authenticated-orcid":false,"given":"Evanthia","family":"Papadopoulou","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,3,25]]},"reference":[{"issue":"6","key":"463_CR1","doi-asserted-by":"publisher","first-page":"591","DOI":"10.1007\/BF02187749","volume":"4","author":"A Aggarwal","year":"1989","unstructured":"Aggarwal, A., Guibas, L.J., Saxe, J., Shor, P.W.: A linear-time algorithm for computing the Voronoi diagram of a convex polygon. Discrete Comput. Geom. 4(6), 591\u2013604 (1989)","journal-title":"Discrete Comput. Geom."},{"key":"463_CR2","doi-asserted-by":"publisher","DOI":"10.1142\/8685","volume-title":"Voronoi Diagrams and Delaunay Triangulations","author":"F Aurenhammer","year":"2013","unstructured":"Aurenhammer, F., Klein, R., Lee, D.-T.: Voronoi Diagrams and Delaunay Triangulations. World Scientific, Hackensack (2013)"},{"issue":"8","key":"463_CR3","doi-asserted-by":"publisher","first-page":"539","DOI":"10.1016\/j.comgeo.2015.04.008","volume":"48","author":"C Bohler","year":"2015","unstructured":"Bohler, C., Cheilaris, P., Klein, R., Liu, Ch.-H., Papadopoulou, E., Zavershynskyi, M.: On the complexity of higher order abstract Voronoi diagrams. Comput. Geom. 48(8), 539\u2013551 (2015)","journal-title":"Comput. Geom."},{"key":"463_CR4","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1016\/j.comgeo.2017.06.013","volume":"68","author":"C Bohler","year":"2018","unstructured":"Bohler, C., Klein, R., Lingas, A., Liu, Ch.-H.: Forest-like abstract Voronoi diagrams in linear time. Comput. Geom. 68, 134\u2013145 (2018)","journal-title":"Comput. Geom."},{"issue":"6","key":"463_CR5","doi-asserted-by":"publisher","first-page":"2317","DOI":"10.1007\/s00453-018-00536-7","volume":"81","author":"C Bohler","year":"2019","unstructured":"Bohler, C., Klein, R., Liu, Ch.-H.: An efficient randomized algorithm for higher-order abstract Voronoi diagrams. Algorithmica 81(6), 2317\u20132345 (2019)","journal-title":"Algorithmica"},{"key":"463_CR6","doi-asserted-by":"crossref","unstructured":"Buchin, K., Devillers, O., Mulzer, W., Schrijvers, O., Shewchuk, J.: Vertex deletion for 3D Delaunay triangulations. In: 21st Annual European Symposium on Algorithms (Sophia Antipolis 2013). Lecture Notes in Comput. Sci., vol. 8125, pp. 253\u2013264. Springer, Heidelberg (2013)","DOI":"10.1007\/978-3-642-40450-4_22"},{"key":"463_CR7","unstructured":"Chew, P.L.: Building Voronoi diagrams for convex polygons in linear expected time. Technical report PCS-TR90-147, Dartmouth College (1990). https:\/\/digitalcommons.dartmouth.edu\/cs_tr\/47\/"},{"issue":"3","key":"463_CR8","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1007\/PL00009429","volume":"21","author":"F Chin","year":"1999","unstructured":"Chin, F., Snoeyink, J., Wang, C.A.: Finding the medial axis of a simple polygon in linear time. Discrete Comput. Geom. 21(3), 405\u2013420 (1999)","journal-title":"Discrete Comput. Geom."},{"key":"463_CR9","unstructured":"Junginger, K., Papadopoulou, E.: Deletion in abstract Voronoi diagrams in expected linear time. In: 34th International Symposium on Computational Geometry (Budapest 2018). Leibniz Int. Proc. Inform., vol. 99, #\u00a050. Leibniz-Zent. Inform., Wadern (2018)"},{"key":"463_CR10","unstructured":"Khramtcova, E., Papadopoulou, E.: An expected linear-time algorithm for the farthest-segment Voronoi diagram (2017). arXiv:1411.2816v3"},{"key":"463_CR11","doi-asserted-by":"crossref","unstructured":"Klein, R.: Concrete and Abstract Voronoi Diagrams. Lecture Notes in Comput. Sci., vol. 400. Springer, Berlin (1989)","DOI":"10.1007\/3-540-52055-4"},{"issue":"9","key":"463_CR12","doi-asserted-by":"publisher","first-page":"885","DOI":"10.1016\/j.comgeo.2009.03.002","volume":"42","author":"R Klein","year":"2009","unstructured":"Klein, R., Langetepe, E., Nilforoushan, Z.: Abstract Voronoi diagrams revisited. Comput. Geom. 42(9), 885\u2013902 (2009)","journal-title":"Comput. Geom."},{"key":"463_CR13","doi-asserted-by":"crossref","unstructured":"Klein, R., Lingas, A.: Hamiltonian abstract Voronoi diagrams in linear time. In: 5th International Symposium on Algorithms and Computation (Beijing 1994). Lecture Notes in Comput. Sci., vol. 834, pp. 11\u201319. Springer, Berlin (1994)","DOI":"10.1007\/3-540-58325-4_161"},{"issue":"3","key":"463_CR14","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1016\/0925-7721(93)90033-3","volume":"3","author":"R Klein","year":"1993","unstructured":"Klein, R., Mehlhorn, K., Meiser, S.: Randomized incremental construction of abstract Voronoi diagrams. Comput. Geom. 3(3), 157\u2013184 (1993)","journal-title":"Comput. Geom."},{"issue":"3","key":"463_CR15","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1515\/dma.1992.2.3.241","volume":"2","author":"VI Levenshtein","year":"1992","unstructured":"Levenshtein, V.I.: Perfect codes in the metric of deletions and insertions. Discrete Math. Appl. 2(3), 241\u2013258 (1992)","journal-title":"Discrete Math. Appl."},{"issue":"6","key":"463_CR16","doi-asserted-by":"publisher","first-page":"583","DOI":"10.1142\/S0218195901000663","volume":"11","author":"K Mehlhorn","year":"2001","unstructured":"Mehlhorn, K., Meiser, S., Rasch, R.: Furthest site abstract Voronoi diagrams. Int. J. Comput. Geom. Appl. 11(6), 583\u2013616 (2001)","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"463_CR17","doi-asserted-by":"publisher","DOI":"10.1002\/9780470317013","volume-title":"Spatial Tessellations: Concepts and Applications of Voronoi Diagrams","author":"A Okabe","year":"2000","unstructured":"Okabe, A., Boots, B., Sugihara, K., Chiu, S.N.: Spatial Tessellations: Concepts and Applications of Voronoi Diagrams. Wiley Series in Probability and Statistics. Wiley, Chichester (2000)"},{"issue":"2","key":"463_CR18","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1007\/s00453-004-1095-0","volume":"40","author":"E Papadopoulou","year":"2004","unstructured":"Papadopoulou, E.: The Hausdorff Voronoi diagram of point clusters in the plane. Algorithmica 40(2), 63\u201382 (2004)","journal-title":"Algorithmica"},{"issue":"6","key":"463_CR19","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1142\/S0218195913600121","volume":"23","author":"E Papadopoulou","year":"2013","unstructured":"Papadopoulou, E., Dey, S.K.: On the farthest line-segment Voronoi diagram. Int. J. Comput. Geom. Appl. 23(6), 443\u2013459 (2013)","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"463_CR20","doi-asserted-by":"crossref","unstructured":"Seidel, R.: Backwards analysis of randomized geometric algorithms. In: New Trends in Discrete and Computational Geometry. Algorithms Combin., vol. 10, pp. 37\u201367. Springer, Berlin (1993)","DOI":"10.1007\/978-3-642-58043-7_3"},{"key":"463_CR21","volume-title":"Davenport\u2013Schinzel Sequences and Their Geometric Applications","author":"M Sharir","year":"1995","unstructured":"Sharir, M., Agarwal, P.K.: Davenport\u2013Schinzel Sequences and Their Geometric Applications. Cambridge University Press, Cambridge (1995)"}],"container-title":["Discrete &amp; Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-022-00463-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00454-022-00463-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-022-00463-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,11]],"date-time":"2023-05-11T05:30:40Z","timestamp":1683783040000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00454-022-00463-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,3,25]]},"references-count":21,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,6]]}},"alternative-id":["463"],"URL":"https:\/\/doi.org\/10.1007\/s00454-022-00463-z","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"type":"print","value":"0179-5376"},{"type":"electronic","value":"1432-0444"}],"subject":[],"published":{"date-parts":[[2023,3,25]]},"assertion":[{"value":"21 July 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 May 2022","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 September 2022","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 March 2023","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}