Strom vyplňující prostor - Space-filling tree

Vesmírné stromy jsou geometrické konstrukce, které jsou analogické křivky vyplňující prostor,^[1] ale mají rozvětvenou stromovou strukturu a jsou zakořeněny. Strom vyplňující prostor je definován přírůstkovým procesem, jehož výsledkem je strom, pro který má každý bod v prostoru cestu konečné délky, která k němu konverguje. Na rozdíl od křivky vyplňující prostor, jednotlivé cesty ve stromu jsou krátké, což umožňuje rychlé dosažení jakékoli části prostoru z kořene.^[2]^[3] Nejjednodušší příklady stromů vyplňujících prostor mají pravidelné, podobné fraktální strukturu, ale lze ji zobecnit na nepravidelnou a rovnoměrnou náhodně /Monte Carlo varianty (viz Rychlé zkoumání náhodného stromu ). Stromy vyplňující prostor mají zajímavé paralely v přírodě, včetně systémy distribuce tekutin, vaskulární sítě, a fraktální růst rostlin a mnoho zajímavých spojení L-systémy v informatice.

Definice

Strom vyplňující prostor je definován iteračním procesem, kdy jediný bod v a kontinuální prostor je spojen kontinuální cestou ke každému dalšímu bodu v prostoru cestou konečný délky a pro každý bod v prostoru existuje alespoň jedna cesta konverguje k tomu.

Pojem „strom vyplňující vesmír“ byl v tomto smyslu vytvořen v technické zprávě z roku 2009 ^[4] který definuje „vyplňování prostoru“ a „strom“ odlišně od jejich tradičních definic v matematice. Jak je vysvětleno v křivka vyplňování prostoru článku, v roce 1890, Peano našel první křivku vyplňování prostoru, a tím Jordan Definice z roku 1887, která je nyní standardní, je křivka jedinou funkcí, nikoli posloupností funkcí. Křivka je „vyplňování prostoru“, protože se jedná o „křivku, jejíž rozsah obsahuje celý čtverec 2-rozměrné jednotky“ (jak je vysvětleno v první větě křivka vyplňování prostoru ).

Naproti tomu strom vyplňující prostor, jak je definován v technické zprávě, není jediný strom. Je to jen sled stromů. Článek uvádí: „Strom vyplňující prostor je ve skutečnosti definován jako nekonečný sled stromů“. Definuje ${ displaystyle T _ { text {square}}}$ jako „sled stromů“, pak uvádí „ ${ displaystyle T _ { text {square}}}$ je strom vyplňující prostor ". Není to vyplňování prostoru ve standardním smyslu zahrnutí celého čtverce 2-dimenzionální jednotky. Místo toho jej papír definuje jako strom v pořadí přicházející libovolně blízko ke každému bodu. Uvádí" Sekvence stromu T se nazývá „vyplňování prostoru“ v prostoru X pokud pro každého X ∈ X, ve stromu existuje cesta, která začíná u kořene a konverguje kXStandardní termín pro tento koncept je ten, že obsahuje sadu bodů, které jsou všude hustý na jednotkovém čtverci.

Příklady

Nejjednodušším příkladem stromu vyplňujícího prostor je strom, který vyplní a náměstí rovinná oblast. Obrázky ilustrují konstrukci pro rovinnou oblast ${ displaystyle [0,1] ^ {2} podmnožina mathbb {R} ^ {2}}$ . Při každé iteraci se ke stávajícím stromům přidají další větve.

Čtvercový prostor vyplňující strom (iterace 1)
Čtvercový strom vyplňující prostor (iterace 2)
Čtvercový strom vyplňující prostor (iterace 3)
Čtvercový strom vyplňující prostor (iterace 4)
Čtvercový prostor vyplňující strom (iterace 5)
Čtvercový strom vyplňující prostor (iterace 6)

Stromy vyplňující prostor lze také definovat pro řadu dalších tvarů a objemů. Níže je schéma dělení používané k definování vyplňování prostoru pro trojúhelníkovou oblast. Při každé iteraci se ke stávajícím stromům spojujícím střed každý trojúhelník do středů čtyř subtriangů.

Schéma členění pro první tři iterace stromu vyplňujícího prostor trojúhelníku

Níže je zobrazeno prvních šest iterací stromu vyplňujícího prostor trojúhelníku:

Strom vyplňující trojúhelník (iterace 1)
Strom vyplňující trojúhelník (iterace 2)
Strom vyplňující trojúhelník (iterace 3)
Strom vyplňující trojúhelníkový prostor (iterace 4)
Strom vyplňující trojúhelník (iterace 5)
Strom vyplňující trojúhelník (iterace 6)

Stromy vyplňující prostor mohou být také konstruovány ve vyšších rozměrech. Nejjednodušší příklady jsou kostky v ${ displaystyle mathbb {R} ^ {3}}$ a hyperkrychle v ${ displaystyle mathbb {R} ^ {n}}$ Podobná posloupnost iterací použitých pro náměstí pro hyperkrychle lze použít strom vyplňující prostor. Třetí iterace takového stromu vyplňujícího prostor ${ displaystyle mathbb {R} ^ {3}}$ je znázorněno níže:

Strom vyplňování prostorů krychlí (iterace 3)

Viz také

Reference

^ Sagan, H. a J. Holbrook: „Křivky vyplňování prostoru“, Springer-Verlag, New York, 1994
^ Kuffner, J. J. a S. M. LaValle: Stromy vyplňující vesmír, The Robotics Institute, Carnegie Mellon University, CMU-RI-TR-09-47, 2009.
^ Kuffner, J. J .; LaValle, S.M .; „Stromy vyplňující prostor: Nový pohled na přírůstkové hledání plánování pohybu,“ Inteligentní roboti a systémy (IROS), 2011, Mezinárodní konference IEEE / RSJ, sv. Č., S. 2199-2206, 25. – 30. Září. 2011
^ Kuffner, J. J. a S. M. LaValle: Stromy vyplňující vesmír, The Robotics Institute, Carnegie Mellon University, CMU-RI-TR-09-47, 2009.

[1] Sagan, H. a J. Holbrook: „Křivky vyplňování prostoru“, Springer-Verlag, New York, 1994

[2] Kuffner, J. J. a S. M. LaValle: Stromy vyplňující vesmír, The Robotics Institute, Carnegie Mellon University, CMU-RI-TR-09-47, 2009.

[3] Kuffner, J. J .; LaValle, S.M .; „Stromy vyplňující prostor: Nový pohled na přírůstkové hledání plánování pohybu,“ Inteligentní roboti a systémy (IROS), 2011, Mezinárodní konference IEEE / RSJ, sv. Č., S. 2199-2206, 25. – 30. Září. 2011

[4] Kuffner, J. J. a S. M. LaValle: Stromy vyplňující vesmír, The Robotics Institute, Carnegie Mellon University, CMU-RI-TR-09-47, 2009.

[1]

[2]

[3]

[4]