Convex hull asymptotic shape evolution

Maxim Arnold; Yuliy Baryshnikov; Steven M. Lavalle

doi:10.1007/978-3-642-36279-8_21

Convex hull asymptotic shape evolution

Maxim Arnold, Yuliy Baryshnikov, Steven M. Lavalle

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

1 Citation (Scopus)

Abstract

The asymptotic properties of Rapidly exploring Random Tree (RRT) growth in large spaces is studied both in simulation and analysis. The main phenomenon is that the convex hull of the RRT reliably evolves into an equilateral triangle when grown in a symmetric planar region (a disk). To characterize this and related phenomena from flocking and swarming, a family of dynamical systems based on incremental evolution in the space of shapes is introduced. Basins of attraction over the shape space explain why the number of hull vertices tends to reduce and the shape stabilizes to a regular polygon with no more than four vertices.

Original language	English
Title of host publication	Springer Tracts in Advanced Robotics
Editors	Emilio Frazzoli, Nicholas Roy, Tomas Lozano-Perez, Daniela Rus
Publisher	Springer Verlag
Pages	349-364
Number of pages	16
ISBN (Print)	9783642362781
DOIs	https://doi.org/10.1007/978-3-642-36279-8_21
Publication status	Published - Jan 1 2013
Externally published	Yes
Event	10th International Workshop on the Algorithmic Foundations of Robotics, WAFR 2012 - Cambridge, United States Duration: Jun 13 2012 → Jun 15 2012

Publication series

Name	Springer Tracts in Advanced Robotics
Volume	86
ISSN (Print)	1610-7438
ISSN (Electronic)	1610-742X

Conference

Conference	10th International Workshop on the Algorithmic Foundations of Robotics, WAFR 2012
Country/Territory	United States
City	Cambridge
Period	6/13/12 → 6/15/12

All Science Journal Classification (ASJC) codes

Electrical and Electronic Engineering
Artificial Intelligence

Access to Document

10.1007/978-3-642-36279-8_21

Cite this

Convex hull asymptotic shape evolution. / Arnold, Maxim; Baryshnikov, Yuliy; Lavalle, Steven M.
Springer Tracts in Advanced Robotics. ed. / Emilio Frazzoli; Nicholas Roy; Tomas Lozano-Perez; Daniela Rus. Springer Verlag, 2013. p. 349-364 (Springer Tracts in Advanced Robotics; Vol. 86).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Arnold, M, Baryshnikov, Y & Lavalle, SM 2013, Convex hull asymptotic shape evolution. in E Frazzoli, N Roy, T Lozano-Perez & D Rus (eds), Springer Tracts in Advanced Robotics. Springer Tracts in Advanced Robotics, vol. 86, Springer Verlag, pp. 349-364, 10th International Workshop on the Algorithmic Foundations of Robotics, WAFR 2012, Cambridge, United States, 6/13/12. https://doi.org/10.1007/978-3-642-36279-8_21

@inproceedings{3eb9162aa51b4caa8df53b1cab57271d,

title = "Convex hull asymptotic shape evolution",

abstract = "The asymptotic properties of Rapidly exploring Random Tree (RRT) growth in large spaces is studied both in simulation and analysis. The main phenomenon is that the convex hull of the RRT reliably evolves into an equilateral triangle when grown in a symmetric planar region (a disk). To characterize this and related phenomena from flocking and swarming, a family of dynamical systems based on incremental evolution in the space of shapes is introduced. Basins of attraction over the shape space explain why the number of hull vertices tends to reduce and the shape stabilizes to a regular polygon with no more than four vertices.",

author = "Maxim Arnold and Yuliy Baryshnikov and Lavalle, {Steven M.}",

year = "2013",

month = jan,

day = "1",

doi = "10.1007/978-3-642-36279-8_21",

language = "English",

isbn = "9783642362781",

series = "Springer Tracts in Advanced Robotics",

publisher = "Springer Verlag",

pages = "349--364",

editor = "Emilio Frazzoli and Nicholas Roy and Tomas Lozano-Perez and Daniela Rus",

booktitle = "Springer Tracts in Advanced Robotics",

address = "Germany",

note = "10th International Workshop on the Algorithmic Foundations of Robotics, WAFR 2012 ; Conference date: 13-06-2012 Through 15-06-2012",

}

TY - GEN

T1 - Convex hull asymptotic shape evolution

AU - Arnold, Maxim

AU - Baryshnikov, Yuliy

AU - Lavalle, Steven M.

PY - 2013/1/1

Y1 - 2013/1/1

N2 - The asymptotic properties of Rapidly exploring Random Tree (RRT) growth in large spaces is studied both in simulation and analysis. The main phenomenon is that the convex hull of the RRT reliably evolves into an equilateral triangle when grown in a symmetric planar region (a disk). To characterize this and related phenomena from flocking and swarming, a family of dynamical systems based on incremental evolution in the space of shapes is introduced. Basins of attraction over the shape space explain why the number of hull vertices tends to reduce and the shape stabilizes to a regular polygon with no more than four vertices.

AB - The asymptotic properties of Rapidly exploring Random Tree (RRT) growth in large spaces is studied both in simulation and analysis. The main phenomenon is that the convex hull of the RRT reliably evolves into an equilateral triangle when grown in a symmetric planar region (a disk). To characterize this and related phenomena from flocking and swarming, a family of dynamical systems based on incremental evolution in the space of shapes is introduced. Basins of attraction over the shape space explain why the number of hull vertices tends to reduce and the shape stabilizes to a regular polygon with no more than four vertices.

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

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

U2 - 10.1007/978-3-642-36279-8_21

DO - 10.1007/978-3-642-36279-8_21

M3 - Conference contribution

AN - SCOPUS:85009476426

SN - 9783642362781

T3 - Springer Tracts in Advanced Robotics

SP - 349

EP - 364

BT - Springer Tracts in Advanced Robotics

A2 - Frazzoli, Emilio

A2 - Roy, Nicholas

A2 - Lozano-Perez, Tomas

A2 - Rus, Daniela

PB - Springer Verlag

T2 - 10th International Workshop on the Algorithmic Foundations of Robotics, WAFR 2012

Y2 - 13 June 2012 through 15 June 2012

ER -

Convex hull asymptotic shape evolution

Abstract

Publication series

Conference

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this