{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:40:57Z","timestamp":1740109257473,"version":"3.37.3"},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"11","license":[{"start":{"date-parts":[[2017,11,3]],"date-time":"2017-11-03T00:00:00Z","timestamp":1509667200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2017,11,3]],"date-time":"2017-11-03T00:00:00Z","timestamp":1509667200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"crossref","award":["0430849"],"award-info":[{"award-number":["0430849"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["1319648","1018370"],"award-info":[{"award-number":["1319648","1018370"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["1229185","0430849"],"award-info":[{"award-number":["1229185","0430849"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000089","name":"Office of International Science and Engineering","doi-asserted-by":"publisher","award":["0334653","0334653"],"award-info":[{"award-number":["0334653","0334653"]}],"id":[{"id":"10.13039\/100000089","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["0081964"],"award-info":[{"award-number":["0081964"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006221","name":"United States - Israel Binational Science Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100006221","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000038","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-0389-y","type":"journal-article","created":{"date-parts":[[2017,11,3]],"date-time":"2017-11-03T15:25:25Z","timestamp":1509722725000},"page":"3316-3334","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Data Structures for Halfplane Proximity Queries and Incremental Voronoi Diagrams"],"prefix":"10.1007","volume":"80","author":[{"given":"Boris","family":"Aronov","sequence":"first","affiliation":[]},{"given":"Prosenjit","family":"Bose","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3803-5703","authenticated-orcid":false,"given":"Erik D.","family":"Demaine","sequence":"additional","affiliation":[]},{"given":"Joachim","family":"Gudmundsson","sequence":"additional","affiliation":[]},{"given":"John","family":"Iacono","sequence":"additional","affiliation":[]},{"given":"Stefan","family":"Langerman","sequence":"additional","affiliation":[]},{"given":"Michiel","family":"Smid","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,11,3]]},"reference":[{"key":"389_CR1","unstructured":"Allen, S., Barba, L., Iacono, J., Langerman, S.: Incremental Voronoi diagrams. Discrete Comput. Geom. (to appear). Special issue of selected papers from the 2016 Symposium on Computational Geometry (SoCG\u201916). \n                    http:\/\/arxiv.org\/abs\/1603.08485"},{"issue":"6","key":"389_CR2","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.B., 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":"389_CR3","doi-asserted-by":"publisher","unstructured":"Chan, T.M.: A dynamic data structure for 3-D convex hulls and 2-D nearest neighbor queries. J. ACM 57(3), Article No. 16 (2010). \n                    https:\/\/doi.org\/10.1145\/1706591.1706596","DOI":"10.1145\/1706591.1706596"},{"key":"389_CR4","volume-title":"Digital Cartography","author":"RG Cromley","year":"1991","unstructured":"Cromley, R.G.: Digital Cartography. Prentice Hall, Upper Saddle River (1991)"},{"issue":"9","key":"389_CR5","doi-asserted-by":"publisher","first-page":"1412","DOI":"10.1109\/5.163409","volume":"80","author":"Y-J Chiang","year":"1992","unstructured":"Chiang, Y.-J., Tamassia, R.: Dynamic algorithms in computational geometry. Proc. IEEE 80(9), 1412\u20131434 (1992)","journal-title":"Proc. IEEE"},{"key":"389_CR6","volume-title":"Computational Geometry: Algorithms and Applications","author":"M de Berg","year":"1999","unstructured":"de Berg, M., van Kreveld, M., Overmars, M., Schwarzkopf, O.: Computational Geometry: Algorithms and Applications, 2nd edn. Springer, Berlin (1999)","edition":"2"},{"key":"389_CR7","volume-title":"Cartography: Thematic Map Design","author":"BD Dent","year":"1998","unstructured":"Dent, B.D.: Cartography: Thematic Map Design, 5th edn. William C Brown Pub, Dubuque (1998)","edition":"5"},{"issue":"3","key":"389_CR8","doi-asserted-by":"publisher","first-page":"174","DOI":"10.1016\/j.comgeo.2005.07.002","volume":"33","author":"O Daescu","year":"2006","unstructured":"Daescu, O., Mi, N., Shin, C.-S., Wolff, A.: Farthest-point queries with geometric and combinatorial constraints. Comput. Geom. Theory Appl. 33(3), 174\u2013185 (2006)","journal-title":"Comput. Geom. Theory Appl."},{"issue":"1","key":"389_CR9","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/0022-0000(89)90034-2","volume":"38","author":"JR Driscoll","year":"1989","unstructured":"Driscoll, J.R., Sarnak, N., Sleator, D.D., Tarjan, R.E.: Making data structures persistent. J. Comput. Syst. Sci. 38(1), 86\u2013124 (1989)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"389_CR10","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1137\/0215023","volume":"15","author":"H Edelsbrunner","year":"1986","unstructured":"Edelsbrunner, H., Guibas, L., Stolfi, J.: Optimal point location in a monotone subdivision. SIAM J. Comput. 15(2), 317\u2013340 (1986)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"389_CR11","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/0925-7721(92)90013-I","volume":"1","author":"D Eppstein","year":"1992","unstructured":"Eppstein, D.: The farthest point Delaunay triangulation minimizes angles. Comput. Geom. Theory Appl. 1(3), 143\u2013148 (1992)","journal-title":"Comput. Geom. Theory Appl."},{"key":"389_CR12","unstructured":"Flarb mania!!. \n                    http:\/\/wave-fan-4ever.tripod.com\/flarbmania\/\n                    \n                   (2004)"},{"key":"389_CR13","volume-title":"Generalization in Digital Cartography","author":"RB McMaster","year":"1992","unstructured":"McMaster, R.B., Shea, K.S.: Generalization in Digital Cartography. Association of American Cartographers, Washington (1992)"},{"key":"389_CR14","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804120","volume-title":"Computational Geometry in C","author":"J O\u2019Rourke","year":"1998","unstructured":"O\u2019Rourke, J.: Computational Geometry in C, 2nd edn. Cambridge University Press, Cambridge (1998)","edition":"2"},{"key":"389_CR15","volume-title":"The Design of Dynamic Data Structures, Volume 156 of Lecture Notes in Computer Science","author":"MH Overmars","year":"1983","unstructured":"Overmars, M.H.: The Design of Dynamic Data Structures, Volume 156 of Lecture Notes in Computer Science. Springer, Berlin (1983)"},{"key":"389_CR16","doi-asserted-by":"crossref","unstructured":"Pettie, Seth: Applications of forbidden 0-1 matrices to search tree and path compression-based data structures. In: Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1457\u20131467 (2010)","DOI":"10.1137\/1.9781611973075.118"},{"key":"389_CR17","volume-title":"Computational Geometry: An Introduction","author":"FP Preparata","year":"1993","unstructured":"Preparata, F.P., Shamos, M.I.: Computational Geometry: An Introduction. Springer, Berlin (1993)"},{"issue":"3","key":"389_CR18","doi-asserted-by":"publisher","first-page":"362","DOI":"10.1016\/0022-0000(83)90006-5","volume":"26","author":"DD Sleator","year":"1983","unstructured":"Sleator, D.D., Tarjan, R.E.: A data structure for dynamic trees. J. Comput. Syst. Sci. 26(3), 362\u2013391 (1983)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"389_CR19","doi-asserted-by":"publisher","first-page":"652","DOI":"10.1145\/3828.3835","volume":"32","author":"DD Sleator","year":"1985","unstructured":"Sleator, D.D., Tarjan, R.E.: Self-adjusting binary search trees. J. ACM 32(3), 652\u2013686 (1985)","journal-title":"J. ACM"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-017-0389-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0389-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0389-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,17]],"date-time":"2020-05-17T06:30:52Z","timestamp":1589697052000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-017-0389-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,11,3]]},"references-count":19,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2018,11]]}},"alternative-id":["389"],"URL":"https:\/\/doi.org\/10.1007\/s00453-017-0389-y","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2017,11,3]]},"assertion":[{"value":"30 September 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 October 2017","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 November 2017","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}