{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,14]],"date-time":"2025-10-14T11:28:03Z","timestamp":1760441283017,"version":"3.40.3"},"publisher-location":"Cham","reference-count":13,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319218397"},{"type":"electronic","value":"9783319218403"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"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":[[2015]]},"DOI":"10.1007\/978-3-319-21840-3_10","type":"book-chapter","created":{"date-parts":[[2015,7,27]],"date-time":"2015-07-27T09:57:38Z","timestamp":1437991058000},"page":"115-126","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Semi-dynamic Connectivity in the Plane"],"prefix":"10.1007","author":[{"given":"Sergio","family":"Cabello","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Kerber","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,7,28]]},"reference":[{"issue":"2","key":"10_CR1","doi-asserted-by":"publisher","first-page":"158","DOI":"10.1002\/ima.20179","volume":"19","author":"K Aizawa","year":"2009","unstructured":"Aizawa, K., Tanaka, S., Motomura, K., Kadowaki, R.: Algorithms for connected component labeling based on quadtrees. International Journal of Imaging Systems and Technology 19(2), 158\u2013166 (2009)","journal-title":"International Journal of Imaging Systems and Technology"},{"key":"10_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1007\/978-3-319-08404-6_4","volume-title":"Algorithm Theory \u2013 SWAT 2014","author":"H Bennett","year":"2014","unstructured":"Bennett, H., Yap, C.: Amortized analysis of smooth quadtrees in all dimensions. In: Ravi, R., G\u00f8rtz, I.L. (eds.) SWAT 2014. LNCS, vol. 8503, pp. 38\u201349. Springer, Heidelberg (2014). doi: 10.1007\/978-3-319-08404-6_4"},{"key":"10_CR3","doi-asserted-by":"crossref","unstructured":"de Berg, M., van Kreveld, M., Overmars, M., Schwarzkopf, O.: Computational Geometry: Algorithms and Applications, 2nd edn. Springer (2000)","DOI":"10.1007\/978-3-662-04245-8"},{"key":"10_CR4","doi-asserted-by":"publisher","unstructured":"Cabello, S., Giannopoulos, P.: The complexity of separating points in the plane. Algorithmica (to appear). doi: 10.1007\/s00453-014-9965-6","DOI":"10.1007\/s00453-014-9965-6"},{"key":"10_CR5","unstructured":"Cormen, T.H., Leiverson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. MIT Press (2009)"},{"key":"10_CR6","unstructured":"Dasgupta, S., Papadimitriou, C.H., Vazirani, U.V.: Algorithms. McGraw-Hill (2008)"},{"issue":"1","key":"10_CR7","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1145\/77635.77639","volume":"9","author":"H Edelsbrunner","year":"1990","unstructured":"Edelsbrunner, H., M\u00fccke, E.P.: Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms. ACM Transactions on Graphics 9(1), 66\u2013104 (1990). doi: 10.1145\/77635.77639","journal-title":"ACM Transactions on Graphics"},{"key":"10_CR8","unstructured":"Erickson, J.: Algorithms notes: Maintaining disjoint sets (\u201cunion-find\u201d) (2015). http:\/\/web.engr.illinois.edu\/ jeffe\/teaching\/algorithms\/"},{"key":"10_CR9","doi-asserted-by":"crossref","unstructured":"Lavalle, S.M.: Planning Algorithms. Cambridge University Press (2006)","DOI":"10.1017\/CBO9780511546877"},{"key":"10_CR10","doi-asserted-by":"crossref","unstructured":"Mohar, B., Thomassen, C.: Graphs on Surfaces. Johns Hopkins University Press (2001)","DOI":"10.56021\/9780801866890"},{"issue":"3","key":"10_CR11","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1137\/S0097539703439088","volume":"34","author":"R Seidel","year":"2005","unstructured":"Seidel, R., Sharir, M.: Top-down analysis of path compression. SIAM Journal of Computing 34(3), 515\u2013525 (2005). doi: 10.1137\/S0097539703439088","journal-title":"SIAM Journal of Computing"},{"issue":"2","key":"10_CR12","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1145\/321879.321884","volume":"22","author":"RE Tarjan","year":"1975","unstructured":"Tarjan, R.E.: Efficiency of a good but not linear set union algorithm. Journal of the ACM 22(2), 215\u2013225 (1975). doi: 10.1145\/321879.321884","journal-title":"Journal of the ACM"},{"key":"10_CR13","doi-asserted-by":"publisher","unstructured":"Wang, C., Chiang, Y.-J., Yap, C.: On soft predicates in subdivision motion planning. In: Proceedings of the Twenty-ninth Annual Symposium on Computational Geometry, SoCG 2013, pp. 349\u2013358. ACM (2013). doi: 10.1145\/2462356.2462386","DOI":"10.1145\/2462356.2462386"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-21840-3_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,10]],"date-time":"2023-02-10T10:46:49Z","timestamp":1676026009000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-21840-3_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319218397","9783319218403"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-21840-3_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"28 July 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}