{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,15]],"date-time":"2026-01-15T04:50:55Z","timestamp":1768452655377,"version":"3.49.0"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2015,9,8]],"date-time":"2015-09-08T00:00:00Z","timestamp":1441670400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2015,12]]},"DOI":"10.1007\/s00454-015-9729-3","type":"journal-article","created":{"date-parts":[[2015,9,8]],"date-time":"2015-09-08T15:03:51Z","timestamp":1441724631000},"page":"871-904","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["Kinetic Voronoi Diagrams and Delaunay Triangulations under Polygonal Distance Functions"],"prefix":"10.1007","volume":"54","author":[{"given":"Pankaj K.","family":"Agarwal","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Haim","family":"Kaplan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Natan","family":"Rubin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Micha","family":"Sharir","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,9,8]]},"reference":[{"key":"9729_CR1","doi-asserted-by":"crossref","first-page":"723","DOI":"10.1007\/s00454-011-9343-y","volume":"45","author":"MA Abam","year":"2011","unstructured":"Abam, M.A., de Berg, M.: Kinetic spanners in $$R^d$$ R d . Discrete Comput. Geom. 45, 723\u2013736 (2011)","journal-title":"Discrete Comput. Geom."},{"key":"9729_CR2","unstructured":"Agarwal, P.K., Gao, J., Guibas, L., Kaplan, H., Koltun, V., Rubin, N., Sharir, M.: Kinetic stable Delaunay graphs. In: Proceedings of the 26th Annual Symposium on Computational Geometry, 2010, pp. 127\u2013136. Also in CoRR (2011). arXiv:1104.0622"},{"key":"9729_CR3","doi-asserted-by":"crossref","unstructured":"Agarwal, P.K., Gao, J., Guibas, L., Kaplan, H., Rubin, N., Sharir, M.: Stable Delaunay graphs. Discrete Comput. Geom (2015). doi: 10.1007\/s00454-015-9730-x","DOI":"10.1007\/s00454-015-9730-x"},{"key":"9729_CR4","doi-asserted-by":"crossref","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, Singapore (2013)"},{"key":"9729_CR5","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1006\/jagm.1998.0988","volume":"31","author":"J Basch","year":"1999","unstructured":"Basch, J., Guibas, L.J., Hershberger, J.: Data structures for mobile data. J. Algorithms 31, 1\u201328 (1999)","journal-title":"J. Algorithms"},{"key":"9729_CR6","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-540-77974-2","volume-title":"Computational Geometry: Algorithms and Applications","author":"M Berg de","year":"2008","unstructured":"de Berg, M., Cheong, O., van Kreveld, M., Overmars, M.: Computational Geometry: Algorithms and Applications, 3rd edn. Springer-Verlag, Berlin (2008)","edition":"3"},{"key":"9729_CR7","doi-asserted-by":"crossref","first-page":"485","DOI":"10.1007\/PL00009366","volume":"19","author":"J-D Boissonnat","year":"1998","unstructured":"Boissonnat, J.-D., Sharir, M., Tagansky, B., Yvinec, M.: Voronoi diagrams in higher dimensions under certain polyhedral distance functions. Discrete Comput. Geom. 19, 485\u2013519 (1998)","journal-title":"Discrete Comput. Geom."},{"key":"9729_CR8","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1016\/0925-7721(95)00044-5","volume":"7","author":"LP Chew","year":"1997","unstructured":"Chew, L.P.: Near-quadratic bounds for the $$L_1$$ L 1 -Voronoi diagram of moving points. Comput. Geom. Theory Appl. 7, 73\u201380 (1997)","journal-title":"Comput. Geom. Theory Appl."},{"key":"9729_CR9","doi-asserted-by":"crossref","unstructured":"Chew, L.P., Drysdale, R.L.: Voronoi diagrams based on convex distance functions. In: Proceedings of the 1st Annual Symposium on Computational Geometry, pp. 235\u2013244 (1985)","DOI":"10.1145\/323233.323264"},{"key":"9729_CR10","unstructured":"Drysdale III, R.L.: A practical algorithm for computing the Delaunay triangulation for convex distance functions. In: Proceedings of the 1st Annual ACM\u2013SIAM Symposium on Discrete Algorithms, pp. 159\u2013168 (1990)"},{"key":"9729_CR11","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-17283-0","volume-title":"CGAL Arrangements and Their Applications: A Step-by-step Guide","author":"E Fogel","year":"2012","unstructured":"Fogel, E., Halperin, D., Wein, R.: CGAL Arrangements and Their Applications: A Step-by-step Guide. Springer-Verlag, Heidelberg (2012)"},{"key":"9729_CR12","first-page":"1117","volume-title":"Handbook of Discrete and Computational Geometry","author":"LJ Guibas","year":"2004","unstructured":"Guibas, L.J.: Modeling motion. In: Goodman, J.E., O\u2019Rourke, J. (eds.) Handbook of Discrete and Computational Geometry, 2nd edn, pp. 1117\u20131134. CRC Press, Boca Raton (2004)","edition":"2"},{"key":"9729_CR13","doi-asserted-by":"crossref","unstructured":"Guibas, L.J., Mitchell, J.S.B., Roos, T.: Voronoi diagrams of moving points in the plane. In: Proceedings of International Workshop on Graph-Theoretic Concepts in Computer Science, pp. 113\u2013125 (1992)","DOI":"10.1007\/3-540-55121-2_11"},{"key":"9729_CR14","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1145\/322123.322124","volume":"26","author":"FK Hwang","year":"1979","unstructured":"Hwang, F.K.: An $$O(n \\log n)$$ O ( n log n ) algorithm for rectilinear minimal spanning trees. J. ACM 26, 177\u2013182 (1979)","journal-title":"J. ACM"},{"issue":"4","key":"9729_CR15","doi-asserted-by":"crossref","first-page":"331","DOI":"10.3233\/FI-1995-2242","volume":"22","author":"C Icking","year":"1995","unstructured":"Icking, C., Klein, R., L\u00ea, N.-M., Ma, L.: Convex distance functions in 3-space are different. Fundam. Inform. 22(4), 331\u2013352 (1995)","journal-title":"Fundam. Inform."},{"key":"9729_CR16","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1007\/BF02187683","volume":"1","author":"K Kedem","year":"1986","unstructured":"Kedem, K., Livne, R., Pach, J., Sharir, M.: On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles. Discrete Comput. Geom. 1, 59\u201370 (1986)","journal-title":"Discrete Comput. Geom."},{"key":"9729_CR17","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1007\/s00454-003-2950-5","volume":"31","author":"V Koltun","year":"2004","unstructured":"Koltun, V., Sharir, M.: Polyhedral Voronoi diagrams of polyhedra in three dimensions. Discrete Comput. Geom. 31, 83\u2013124 (2004)","journal-title":"Discrete Comput. Geom."},{"key":"9729_CR18","doi-asserted-by":"crossref","first-page":"604","DOI":"10.1145\/322217.322219","volume":"27","author":"D-T Lee","year":"1980","unstructured":"Lee, D.-T.: Two-dimensional Voronoi diagrams in the $$L_p$$ L p -metric. J. ACM 27, 604\u2013618 (1980)","journal-title":"J. ACM"},{"key":"9729_CR19","doi-asserted-by":"crossref","first-page":"200","DOI":"10.1137\/0209017","volume":"9","author":"D-T Lee","year":"1980","unstructured":"Lee, D.-T., Wong, C.K.: Voronoi diagrams in $$L_1$$ L 1 ( $$L_\\infty $$ L \u221e ) metrics with 2-dimensional storage applications. SIAM J. Comput. 9, 200\u2013211 (1980)","journal-title":"SIAM J. Comput."},{"key":"9729_CR20","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1007\/BF02187867","volume":"2","author":"D Leven","year":"1987","unstructured":"Leven, D., Sharir, M.: Planning a purely translational motion for a convex object in two-dimensional space using generalized Voronoi diagrams. Discrete Comput. Geom. 2, 9\u201331 (1987)","journal-title":"Discrete Comput. Geom."},{"key":"9729_CR21","unstructured":"Ma, L.: Bisectors and Voronoi diagrams for convex distance functions. PhD Thesis, Fern University, Hagen (2000). https:\/\/www.fernuni-hagen.de\/ks\/download\/pub\/tr267.pdf"},{"issue":"4","key":"9729_CR22","doi-asserted-by":"crossref","first-page":"710","DOI":"10.1007\/s00454-013-9512-2","volume":"49","author":"N Rubin","year":"2013","unstructured":"Rubin, N.: On topological changes in the Delaunay triangulation of moving points. Discrete Comput. Geom. 49(4), 710\u2013746 (2013)","journal-title":"Discrete Comput. Geom."},{"key":"9729_CR23","doi-asserted-by":"crossref","unstructured":"Rubin, N.: On kinetic Delaunay triangulations: A near quadratic bound for unit speed motions. In: Proceedings of 54th Annual IEEE Symposium on Foundations of Computer Science, pp. 519\u2013528 (2013). Also in J. ACM, to appear","DOI":"10.1109\/FOCS.2013.62"},{"key":"9729_CR24","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, New York (1995)"},{"key":"9729_CR25","doi-asserted-by":"crossref","unstructured":"Skyum, S.: A sweepline algorithm for generalized Delaunay triangulations. Technical Report, DAIMI PB-373, Computer Science Department, Aarhus University, Aarhus (1991)","DOI":"10.7146\/dpb.v20i373.6605"},{"key":"9729_CR26","doi-asserted-by":"crossref","first-page":"728","DOI":"10.1137\/0216049","volume":"16","author":"P Widmayer","year":"1987","unstructured":"Widmayer, P., Wu, Y.-F., Wong, C.K.: On some distance problems in fixed orientations. SIAM J. Comput. 16, 728\u2013746 (1987)","journal-title":"SIAM J. Comput."},{"key":"9729_CR27","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1016\/0022-0000(90)90016-E","volume":"40","author":"CK Yap","year":"1990","unstructured":"Yap, C.K.: A geometric consistency theorem for a symbolic perturbation scheme. J. Comput. Syst. Sci. 40, 2\u201318 (1990)","journal-title":"J. Comput. Syst. Sci."}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-015-9729-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00454-015-9729-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-015-9729-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,9,8]],"date-time":"2020-09-08T03:26:32Z","timestamp":1599535592000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00454-015-9729-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,9,8]]},"references-count":27,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2015,12]]}},"alternative-id":["9729"],"URL":"https:\/\/doi.org\/10.1007\/s00454-015-9729-3","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,9,8]]}}}