The convergence of bird flocking

Bernard Chazelle

doi:10.1145/2629613

The convergence of bird flocking

Bernard Chazelle

Research output: Contribution to journal › Article › peer-review

30 Scopus citations

Abstract

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.

Original language	English (US)
Article number	21
Journal	Journal of the ACM
Volume	61
Issue number	4
DOIs	https://doi.org/10.1145/2629613
State	Published - Jul 2014
Externally published	Yes

All Science Journal Classification (ASJC) codes

Software
Control and Systems Engineering
Information Systems
Hardware and Architecture
Artificial Intelligence

Keywords

Dynamic systems
Natural algorithms

Access to Document

10.1145/2629613

Cite this

@article{b98e255501e7492b935f73f55dcba15a,

title = "The convergence of bird flocking",

abstract = "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.",

keywords = "Dynamic systems, Natural algorithms",

author = "Bernard Chazelle",

year = "2014",

month = jul,

doi = "10.1145/2629613",

language = "English (US)",

volume = "61",

journal = "Journal of the ACM",

issn = "0004-5411",

publisher = "Association for Computing Machinery (ACM)",

number = "4",

}

TY - JOUR

T1 - The convergence of bird flocking

AU - Chazelle, Bernard

PY - 2014/7

Y1 - 2014/7

N2 - 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.

AB - 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.

KW - Dynamic systems

KW - Natural algorithms

UR - http://www.scopus.com/inward/record.url?scp=84906221060&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84906221060&partnerID=8YFLogxK

U2 - 10.1145/2629613

DO - 10.1145/2629613

M3 - Article

AN - SCOPUS:84906221060

SN - 0004-5411

VL - 61

JO - Journal of the ACM

JF - Journal of the ACM

IS - 4

M1 - 21

ER -

The convergence of bird flocking

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this