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

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

Определение

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

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

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

Примеры

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

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

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

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

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

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

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

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

См. также

• H-дерево
• Кривая Пеано
• Быстро растущее случайное дерево (RRTs)
• Двоичное разбиение пространства

Литература

• H. Sagan. Space-filling curves. — New York: Springer-Verlag, 1994. — (Universitext). — ISBN 0-387-94265-3.
• J.J. Kuffner , S.M. LaValle. Space-filling Trees : Технический отчёт. — The Robotics Institute, Carnegie Mellon University,, 2009. — № CMU-RI-TR-09-47.
• J.J. Kuffner , S.M. LaValle. Intelligent Robots and Systems (IROS), 2011 IEEE/RSJ International Conference. — 2011. — С. 2199—2206.