Заполняющее пространство дерево

Заполняющие пространство деревья — это геометрические построения, аналогичные кривым Пеано, но имеет ветвящуюся подобно дереву структуру и корень. Заполняющее пространство дерево определяется пошаговым процессом, который даёт дерево, в котором любая точка пространства имеет конечной длины путь, который сходится к данной точке. В отличие от заполняющих пространство кривых, каждый путь в дереве короток, что позволяет любую часть пространства достичь из корня . Простейшие примеры заполняющих пространство деревьев имеют регулярную, самоподобную, фрактальную) структуру, но могут быть обобщены до нерегулярных, и даже до случайных/получаемых методом Монте-Карло вариантов (см. «Быстро растущее случайное дерево»). Заполняющие пространство деревья имеют интересные параллели в природе, такие как распределение потоков жидкостей, сосудистая сеть, фрактальный рост растений и много интересных связей с L-системами в информатике.

Определение

Заполняющее пространство дерево определяется пошаговым процессом, который даёт дерево, в котором любая точка непрерывного пространства связана непрерывным путём с любой другой точкой пространства путём конечной длины и для любой точки пространства существует по меньшей мере один путь, который сходится к ней.

Термин «заполняющее пространство дерево» в обсуждаемом смысле было введено в техническом отчёте 2009 года Куффнера и ЛаВелле, в котором термины «заполнение пространства» и «дерево» определяются несколько отлично от традиционного принятого в математике подхода. Как указано в статье «Кривая Пеано», в 1890-ом году Пеано нашёл первую заполняющую пространство кривую, и по определению Жордана 1887-го года, которое сейчас является стандартом, кривая задаётся одной функцией, а не последовательностью функций. Кривая является «заполняющей пространство», поскольку это «кривая, образ которой содержит весь 2-мерный единичный квадрат» (как указано в первом предложении статьи «Кривая Пеано»).

В отличие от этого, заполняющее пространство дерево, как определено в отчёте, не является одним деревом, это только последовательность деревьев. В отчёте говорится: «Заполняющее пространство дерево, фактически, определяется как бесконечная последовательность деревьев». В статье определяется T s q u a r e {displaystyle T_{square}} как «последовательность деревьев», затем утверждается « T s q u a r e {displaystyle T_{square}} является заполняющим пространство деревом». Дерево не является заполняющим пространство в стандартном смысле включения всего 2-мерного квадрата. Вместо этого в статье определяется этот термин как свойство последовательности деревьев подойти как угодно близко к любой точке пространства. Статья утверждает: «Последовательность деревьев T называется “заполняющей пространство” в пространстве X, если для любой точки x из X существует путь в дереве, начинающийся в корне и сходящийся к x.». Стандартный термин для этого понятия предполагает, что объект включает множество точек, всюду плотное в единичном квадрате.

Примеры

Простейший пример заполняющего пространство дерева — это дерево, заполняющее квадрат на плоскости. Рисунки иллюстрируют построение для плоской области [ 0 , 1 ] 2 ⊂ ℜ 2 {displaystyle [0,1]^{2}subset Re ^{2}} . На каждой итерации добавляются дополнительные ветви к существующим деревьям.

Итерация 1
Итерация 2
Итерация 3
Итерация 4
Итерация 5
Итерация 6

Заполняющие пространство деревья можно определить для других фигур и тел. Ниже показана схема для дерева в треугольной области. На каждой итерации добавляются ветки, соединяющие центр каждого треугольника с центрами четырёх подтреугольников.

Схема деления первых трёх итераций для треугольного заполняющего пространство дерева.

Первые шесть итераций треугольного заполняющего пространство дерева:

Итерация 1
Итерация 2
Итерация 3
Итерация 4
Итерация 5
Итерация 6

Заполняющие пространство деревья можно строить для пространств больших размерностей. Простейшие примеры — куб в ℜ 3 {displaystyle Re ^{3}} и гиперкуб в ℜ n {displaystyle Re ^{n}} . Последовательность шагов, похожая на итерации для заполняющего пространство дерева в квадрате, может быть использована для гиперкубов. Ниже проиллюстрирована третья итерация построения заполняющего пространство дерева в ℜ 3 {displaystyle Re ^{3}} :

Заполняющее куб дерево (Итерация 3)