{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,15]],"date-time":"2026-01-15T04:02:43Z","timestamp":1768449763359,"version":"3.49.0"},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2015,6,30]],"date-time":"2015-06-30T00:00:00Z","timestamp":1435622400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100014086","name":"Fondation Sciences Math\u00e9matiques de Paris","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100014086","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Minerva Fellowship Program of the Max Planck Society"},{"name":"public grant overseen by the French National Research Agency (ANR) as part of the Investissements d'Avenir program","award":["ANR-10-LABX-0098"],"award-info":[{"award-number":["ANR-10-LABX-0098"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2015,6,30]]},"abstract":"<jats:p>\n            Let\n            <jats:italic>P<\/jats:italic>\n            be a collection of\n            <jats:italic>n<\/jats:italic>\n            points in the plane, each moving along some straight line at unit speed. We obtain an almost tight upper bound of\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2+\u03f5<\/jats:sup>\n            ), for any \u03f5 &gt; 0, on the maximum number of discrete changes that the Delaunay triangulation DT(\n            <jats:italic>P<\/jats:italic>\n            ) of\n            <jats:italic>P<\/jats:italic>\n            experiences during this motion. Our analysis is cast in a purely topological setting, where we only assume that (i) any four points can be co-circular at most three times, and (ii) no triple of points can be collinear more than twice; these assumptions hold for unit speed motions.\n          <\/jats:p>","DOI":"10.1145\/2746228","type":"journal-article","created":{"date-parts":[[2015,7,6]],"date-time":"2015-07-06T14:04:16Z","timestamp":1436191456000},"page":"1-85","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["On Kinetic Delaunay Triangulations"],"prefix":"10.1145","volume":"62","author":[{"given":"Natan","family":"Rubin","sequence":"first","affiliation":[{"name":"Ben-Gurion University of The Negev, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2015,6,30]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02716576"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1810959.1810984"},{"key":"e_1_2_2_3_1","unstructured":"P. K. Agarwal J. Gao L. J. Guibas H. Kaplan N. Rubin and M. Sharir. 2015. Stable Delaunay graphs. http:\/\/arxiv.org\/abs\/1504.06851.  P. K. Agarwal J. Gao L. J. Guibas H. Kaplan N. Rubin and M. Sharir. 2015. Stable Delaunay graphs. http:\/\/arxiv.org\/abs\/1504.06851."},{"key":"e_1_2_2_4_1","unstructured":"P. K. Agarwal H. Kaplan N. Rubin and M. Sharir. 2014. Kinetic Voronoi diagrams and Delaunay triangulations under polygonal distance functions. http:\/\/arxiv.org\/abs\/1404.4851.  P. K. Agarwal H. Kaplan N. Rubin and M. Sharir. 2014. Kinetic Voronoi diagrams and Delaunay triangulations under polygonal distance functions. http:\/\/arxiv.org\/abs\/1404.4851."},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-006-1266-7"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1983.13"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/0898-1221(85)90105-1"},{"key":"e_1_2_2_8_1","doi-asserted-by":"crossref","unstructured":"F. Aurenhammer and R. Klein. 2000. Voronoi diagrams. In Handbook of Computational Geometry J.-R. Sack and J. Urrutia Eds. Elsevier Amsterdam The Netherlands 201--290.  F. Aurenhammer and R. Klein. 2000. Voronoi diagrams. In Handbook of Computational Geometry J.-R. Sack and J. Urrutia Eds. Elsevier Amsterdam The Netherlands 201--290.","DOI":"10.1016\/B978-044482537-7\/50006-1"},{"key":"e_1_2_2_9_1","doi-asserted-by":"crossref","unstructured":"F. Aurenhammer R. Klein and D. T. Lee. 2013. Voronoi Diagrams and Delaunay Triangulations. World Scientific Publishing Company Singapore.   F. Aurenhammer R. Klein and D. T. Lee. 2013. Voronoi Diagrams and Delaunay Triangulations. World Scientific Publishing Company Singapore.","DOI":"10.1142\/8685"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1706591.1706596"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(95)00044-5"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187740"},{"key":"e_1_2_2_13_1","first-page":"793","article-title":"Sur la sphere vide. A la memoire de Georges Vonoroi","volume":"7","author":"Delaunay B.","year":"1934","journal-title":"Izv. Akad. Nauk. SSSR. Otdelenie Matematicheskih I Estestvennyh Nauk"},{"key":"e_1_2_2_14_1","unstructured":"E. D. Demaine J. S. B. Mitchell and J. O'Rourke The Open Problems Project http:\/\/www.cs.smith.edu\/&sim;orourke\/TOPP\/.  E. D. Demaine J. S. B. Mitchell and J. O'Rourke The Open Problems Project http:\/\/www.cs.smith.edu\/&sim;orourke\/TOPP\/."},{"key":"e_1_2_2_15_1","doi-asserted-by":"crossref","unstructured":"H. Edelsbrunner. 2001. Geometry and Topology for Mesh Generation. Cambridge University Press Cambridge.   H. Edelsbrunner. 2001. Geometry and Topology for Mesh Generation. Cambridge University Press Cambridge.","DOI":"10.1017\/CBO9780511530067"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/77635.77639"},{"key":"e_1_2_2_17_1","volume-title":"Handbook of Discrete and Computational Geometry","author":"Fortune S.","edition":"2"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195991000037"},{"key":"e_1_2_2_19_1","volume-title":"Proceedings of th 17th International Workshop on Graph-Theoretical Concepts of Computer Science. Lecture Notes in Computer Science","volume":"570","author":"Guibas L. J."},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02574383"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2010.11.001"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702408387"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753970240700X"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-013-9512-2"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02574384"},{"key":"e_1_2_2_26_1","unstructured":"M. Sharir and P. K. Agarwal. 1995. Davenport-Schinzel Sequences and Their Geometric Applications.Cambridge University Press.   M. Sharir and P. K. Agarwal. 1995. Davenport-Schinzel Sequences and Their Geometric Applications.Cambridge University Press."},{"key":"e_1_2_2_27_1","doi-asserted-by":"crossref","unstructured":"G. F. Voronoi. 1908. Nouvelles applications des parameters continus \u00e0 la th\u00e9orie de forms quadratiques. J. f\u00fcr die reine und angewandte Mathematik 134 198--287.  G. F. Voronoi. 1908. Nouvelles applications des parameters continus \u00e0 la th\u00e9orie de forms quadratiques. J. f\u00fcr die reine und angewandte Mathematik 134 198--287.","DOI":"10.1515\/crll.1908.134.198"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2746228","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2746228","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:16:44Z","timestamp":1750227404000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2746228"}},"subtitle":["A Near-Quadratic Bound for Unit Speed Motions"],"short-title":[],"issued":{"date-parts":[[2015,6,30]]},"references-count":27,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015,6,30]]}},"alternative-id":["10.1145\/2746228"],"URL":"https:\/\/doi.org\/10.1145\/2746228","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,6,30]]},"assertion":[{"value":"2014-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-06-30","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}