{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,13]],"date-time":"2026-05-13T14:28:14Z","timestamp":1778682494451,"version":"3.51.4"},"reference-count":34,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2014,7,1]],"date-time":"2014-07-01T00:00:00Z","timestamp":1404172800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-0634958, NSF CCF-0832797"],"award-info":[{"award-number":["CCF-0634958, NSF CCF-0832797"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2014,7]]},"abstract":"<jats:p>We bound the time it takes for a group of birds to stabilize in a standard flocking model. Each bird averages its velocity with its neighbors lying within a fixed radius. We resolve the worst-case complexity of this natural algorithm by providing asymptotically tight bounds on the time to equilibrium. We reduce the problem to two distinct questions in computational geometry and circuit complexity.<\/jats:p>","DOI":"10.1145\/2629613","type":"journal-article","created":{"date-parts":[[2014,8,12]],"date-time":"2014-08-12T13:53:48Z","timestamp":1407851628000},"page":"1-35","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":27,"title":["The Convergence of Bird Flocking"],"prefix":"10.1145","volume":"61","author":[{"given":"Bernard","family":"Chazelle","sequence":"first","affiliation":[{"name":"Princeton University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2014,7]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0711437105"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-34611-8_6"},{"key":"e_1_2_1_3_1","unstructured":"Camazine S. Deneubourg J.-L. Franks N. Sneyd J. Theraulaz G. and Bonabeau E. 2003. Self-Organization in Biological Systems. Princeton University Press Princeton N.J.   Camazine S. Deneubourg J.-L. Franks N. Sneyd J. Theraulaz G. and Bonabeau E. 2003. Self-Organization in Biological Systems . Princeton University Press Princeton N.J."},{"key":"e_1_2_1_4_1","volume-title":"Complexity of Robot Motion Planning","author":"Canny J.","unstructured":"Canny , J. 1988. Complexity of Robot Motion Planning . The MIT Press . Canny, J. 1988. Complexity of Robot Motion Planning. The MIT Press."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1005766107"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2007.06.007"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2008.03.002"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2012.07.005"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/100791671"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.70"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2380656.2380679"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-008-2244-x"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1993.1052"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 17th International Symposium on Mathematical Theory of Networks and Systems (MTNS\u201906)","author":"Hendrickx J.","unstructured":"Hendrickx , J. and Blondel , V . 2006. Convergence of different linear and non-linear vicsek models . In Proceedings of the 17th International Symposium on Mathematical Theory of Networks and Systems (MTNS\u201906) . 1229--1240. Hendrickx, J. and Blondel, V. 2006. Convergence of different linear and non-linear vicsek models. In Proceedings of the 17th International Symposium on Mathematical Theory of Networks and Systems (MTNS\u201906). 1229--1240."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(01)00208-6"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2007.900638"},{"key":"e_1_2_1_17_1","unstructured":"Kemeny J. and Snell J. 1983. Finite Markov Chains. Springer.  Kemeny J. and Snell J. 1983. Finite Markov Chains . Springer."},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","DOI":"10.1103\/PhysRevA.85.043603","article-title":"Superdiffusive nonequilibrium motion of an impurity in a fermi sea","author":"Kim H.","year":"2012","unstructured":"Kim , H. and Huse , D. 2012 . Superdiffusive nonequilibrium motion of an impurity in a fermi sea . Phys. Rev. A 85. Kim, H. and Huse, D. 2012. Superdiffusive nonequilibrium motion of an impurity in a fermi sea. Phys. Rev. A 85.","journal-title":"Phys. Rev. A 85."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(81)90003-3"},{"key":"e_1_2_1_20_1","unstructured":"Li S. and Wang H. 2004. Multi-agent coordination using nearest neighbor rules: Revisiting the Vicsek model. arXiv:cs\/0407021v2.  Li S. and Wang H. 2004. Multi-agent coordination using nearest neighbor rules: Revisiting the Vicsek model. arXiv:cs\/0407021v2."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2004.841888"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the 44th IEEE Conference on Decision and Control and European Control Conference (ECC-CDC\u201905)","author":"Moshtagh N.","unstructured":"Moshtagh , N. , Jadbabaie , A. , and Daniilidis , K . 2005. Distributed geodesic control laws for flocking of nonholonomic agents . In Proceedings of the 44th IEEE Conference on Decision and Control and European Control Conference (ECC-CDC\u201905) . Moshtagh, N., Jadbabaie, A., and Daniilidis, K. 2005. Distributed geodesic control laws for flocking of nonholonomic agents. In Proceedings of the 44th IEEE Conference on Decision and Control and European Control Conference (ECC-CDC\u201905)."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2005.864190"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/37402.37406"},{"key":"e_1_2_1_25_1","volume-title":"Non-Negative Matrices and Markov Chains","author":"Seneta E.","unstructured":"Seneta , E. 2006. Non-Negative Matrices and Markov Chains . 2 nd Ed., Springer . Seneta, E. 2006. Non-Negative Matrices and Markov Chains. 2nd Ed., Springer.","edition":"2"},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the IEEE International Symposium on Intelligent Control. 1423--1428","author":"Shi H.","unstructured":"Shi , H. , Wang , L. , and Chu , T . 2005. Coordination of multiple dynamic agents with asymmetric interactions . In Proceedings of the IEEE International Symposium on Intelligent Control. 1423--1428 . Shi, H., Wang, L., and Chu, T. 2005. Coordination of multiple dynamic agents with asymmetric interactions. In Proceedings of the IEEE International Symposium on Intelligent Control. 1423--1428."},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the American Control Conference (ACC\u201907)","author":"Tahbaz-Salehi A.","unstructured":"Tahbaz-Salehi , A. and Jadbabaie , A . 2007. Bounds for eigenvalues of certain stochastic matrices. On recurrence of graph connectivity in Vicsek\u2019s model of motion coordination for mobile autonomous agents . In Proceedings of the American Control Conference (ACC\u201907) . 699--704. Tahbaz-Salehi, A. and Jadbabaie, A. 2007. Bounds for eigenvalues of certain stochastic matrices. On recurrence of graph connectivity in Vicsek\u2019s model of motion coordination for mobile autonomous agents. In Proceedings of the American Control Conference (ACC\u201907). 699--704."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11424-007-9016-3"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/2645912.2646059"},{"key":"e_1_2_1_30_1","volume-title":"Proceedings of the IEEE Conference on Decision and Control","author":"Tanner H.","year":"2016","unstructured":"Tanner , H. , Jadbabaie , A. , and Pappas , G . 2003b. Stable flocking of mobile agents, Part II: Dynamic topology . In Proceedings of the IEEE Conference on Decision and Control , Maui, Hawaii. 2016 --2021. Tanner, H., Jadbabaie, A., and Pappas, G. 2003b. Stable flocking of mobile agents, Part II: Dynamic topology. In Proceedings of the IEEE Conference on Decision and Control, Maui, Hawaii. 2016--2021."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2007.895948"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(90)90287-R"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.75.1226"},{"key":"e_1_2_1_34_1","volume-title":"Fundamental Problems of Algorithmic Algebra","author":"Yap C.","unstructured":"Yap , C. 2000. Fundamental Problems of Algorithmic Algebra . Oxford University Press, Inc. , New York . Yap, C. 2000. Fundamental Problems of Algorithmic Algebra. Oxford University Press, Inc., New York."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2629613","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2629613","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:13:29Z","timestamp":1750227209000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2629613"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,7]]},"references-count":34,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2014,7]]}},"alternative-id":["10.1145\/2629613"],"URL":"https:\/\/doi.org\/10.1145\/2629613","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,7]]},"assertion":[{"value":"2009-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-07-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}