{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:35:14Z","timestamp":1759638914771,"version":"3.37.3"},"reference-count":11,"publisher":"Springer Science and Business Media LLC","issue":"11","license":[{"start":{"date-parts":[[2017,9,19]],"date-time":"2017-09-19T00:00:00Z","timestamp":1505779200000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100002790","name":"Canadian Network for Research and Innovation in Machining Technology, Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100002790","id-type":"DOI","asserted-by":"publisher"}]},{"name":"NSF grant","award":["CCF-1228639"],"award-info":[{"award-number":["CCF-1228639"]}]},{"DOI":"10.13039\/501100002790","name":"Canadian Network for Research and Innovation in Machining Technology, Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100002790","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002790","name":"Canadian Network for Research and Innovation in Machining Technology, Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100002790","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2018,11]]},"DOI":"10.1007\/s00453-017-0375-4","type":"journal-article","created":{"date-parts":[[2017,9,19]],"date-time":"2017-09-19T10:59:17Z","timestamp":1505818757000},"page":"3177-3191","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Spanning Trees in Multipartite Geometric Graphs"],"prefix":"10.1007","volume":"80","author":[{"given":"Ahmad","family":"Biniaz","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Prosenjit","family":"Bose","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Eppstein","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anil","family":"Maheshwari","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pat","family":"Morin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michiel","family":"Smid","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,9,19]]},"reference":[{"issue":"1","key":"375_CR1","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1016\/0020-0190(92)90133-G","volume":"42","author":"A Aggarwal","year":"1992","unstructured":"Aggarwal, A., Edelsbrunner, H., Raghavan, P., Tiwari, P.: Optimal time bounds for some proximity problems in the plane. Inf. Process. Lett. 42(1), 55\u201360 (1992)","journal-title":"Inf. Process. Lett."},{"key":"375_CR2","doi-asserted-by":"crossref","first-page":"591","DOI":"10.1007\/BF02187749","volume":"4","author":"A Aggarwal","year":"1989","unstructured":"Aggarwal, A., Guibas, L.J., Saxe, J.B., Shor, P.W.: A linear-time algorithm for computing the Voronoi diagram of a convex polygon. Discrete Comput. Geom. 4, 591\u2013604 (1989)","journal-title":"Discrete Comput. Geom."},{"key":"375_CR3","unstructured":"Avis, D.: Lower bounds for geometric problems. In: 18th Allerton Conference, Urbana, IL, pp. 35\u201340 (1980)"},{"issue":"1","key":"375_CR4","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1007\/s00453-002-0939-8","volume":"34","author":"B Chazelle","year":"2002","unstructured":"Chazelle, B., Devillers, O., Hurtado, F., Mora, M., Sacrist\u00e1n, V., Teillaud, M.: Splitting a Delaunay triangulation in linear time. Algorithmica 34(1), 39\u201346 (2002)","journal-title":"Algorithmica"},{"issue":"4","key":"375_CR5","doi-asserted-by":"crossref","first-page":"1326","DOI":"10.1137\/S0097539796313490","volume":"28","author":"BV Cherkassky","year":"1999","unstructured":"Cherkassky, B.V., Goldberg, A.V., Silverstein, C.: Buckets, heaps, lists, and monotone priority queues. SIAM J. Comput. 28(4), 1326\u20131346 (1999)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"375_CR6","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1016\/0196-6774(85)90039-2","volume":"6","author":"H Edelsbrunner","year":"1985","unstructured":"Edelsbrunner, H.: Computing the extreme distances between two convex polygons. J. Algorithms 6(2), 213\u2013224 (1985)","journal-title":"J. Algorithms"},{"key":"375_CR7","doi-asserted-by":"crossref","unstructured":"Kaplan, H., Mulzer, W., Roditty, L., Seiferth, P., Sharir, M.: Dynamic planar Voronoi diagrams for general distance functions and their algorithmic applications. In: Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (\n                        $$SODA$$\n                        \n                            \n                                \n                                    S\n                                    O\n                                    D\n                                    A\n                                \n                            \n                        \n                    ), pp. 2495\u20132504 (2017)","DOI":"10.1137\/1.9781611974782.165"},{"key":"375_CR8","doi-asserted-by":"crossref","unstructured":"Kirkpatrick, D.G.: Efficient computation of continuous skeletons. In: 20th Annual Symposium on Foundations of Computer Science, pp. 18\u201327 (1979)","DOI":"10.1109\/SFCS.1979.15"},{"issue":"4","key":"375_CR9","doi-asserted-by":"crossref","first-page":"941","DOI":"10.1137\/110825698","volume":"41","author":"M L\u00f6ffler","year":"2012","unstructured":"L\u00f6ffler, M., Mulzer, W.: Triangulating the square and squaring the triangle: quadtrees and Delaunay triangulations are equivalent. SIAM J. Comput. 41(4), 941\u2013974 (2012)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"375_CR10","doi-asserted-by":"crossref","first-page":"407","DOI":"10.1007\/BF01840396","volume":"5","author":"CL Monma","year":"1990","unstructured":"Monma, C.L., Paterson, M., Suri, S., Yao, F.F.: Computing Euclidean maximum spanning trees. Algorithmica 5(3), 407\u2013419 (1990)","journal-title":"Algorithmica"},{"key":"375_CR11","series-title":"Texts and Monographs in Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry\u2014An Introduction","author":"FP Preparata","year":"1985","unstructured":"Preparata, F.P., Shamos, M.I.: Computational Geometry\u2014An Introduction. Texts and Monographs in Computer Science. Springer, Berlin (1985)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-017-0375-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0375-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0375-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2018,8,6]],"date-time":"2018-08-06T12:57:54Z","timestamp":1533560274000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-017-0375-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,9,19]]},"references-count":11,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2018,11]]}},"alternative-id":["375"],"URL":"https:\/\/doi.org\/10.1007\/s00453-017-0375-4","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2017,9,19]]}}}