Дерево, заполняющее пространство

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

Определение

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

Концепция «дерева, заполняющего пространство» в этом смысле была описана в главе 15 « влиятельной книги Мандельброта Фрактальная геометрия природы» (1982). Концепция была сделана более строгой и получила название «дерево, заполняющее пространство» в техническом отчете 2009 года. это определяет «заполнение пространства» и «дерево» иначе, чем их традиционные определения в математике. Как поясняется в статье о кривой, заполняющей пространство , в 1890 году Пеано нашел первую кривую, заполняющую пространство, и согласно определению Джордана 1887 года, которое сейчас является стандартным, кривая — это отдельная функция, а не последовательность функций. Кривая является «заполняющей пространство», потому что это «кривая, диапазон которой содержит весь двумерный единичный квадрат» (как объяснено в первом предложении кривой, заполняющей пространство ).

Напротив, дерево, заполняющее пространство, как оно определено в техническом отчете, не является единым деревом. Это всего лишь последовательность деревьев. В документе говорится: «Дерево, заполняющее пространство, на самом деле определяется как бесконечная последовательность деревьев». Он определяет $T_{\text{square}}$ как «последовательность деревьев», затем утверждается: « $T_{\text{square}}$ Это дерево, заполняющее пространство». Это не заполнение пространства в стандартном смысле, включающее в себя весь двумерный единичный квадрат. Вместо этого в статье оно определяется как наличие деревьев в последовательности, приближающихся сколь угодно близко к каждой точке. В нем говорится: « Древовидная последовательность T называется «заполнением пространства» в пространстве X , если для каждого x ∈ X существует путь в дереве, который начинается в корне и сходится к x ». Стандартный термин для этого понятия состоит в том, что он включает в себя множество точек, плотное всюду на единичном квадрате.

Примеры

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

• 
  Дерево, заполняющее квадратное пространство (итерация 1)
• 
  Дерево, заполняющее квадратное пространство (итерация 2)
• 
  Дерево, заполняющее квадратное пространство (итерация 3)
• 
  Дерево, заполняющее квадратное пространство (итерация 4)
• 
  Дерево, заполняющее квадратное пространство (итерация 5)
• 
  Дерево, заполняющее квадратное пространство (итерация 6)

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

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

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

• 
  Дерево заполнения пространства треугольником (итерация 1)
• 
  Дерево заполнения пространства треугольником (итерация 2)
• 
  Дерево заполнения пространства треугольником (итерация 3)
• 
  Дерево заполнения пространства треугольником (итерация 4)
• 
  Дерево заполнения пространства треугольником (итерация 5)
• 
  Дерево заполнения пространства треугольником (итерация 6)

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

• 
  Дерево заполнения пространства куба (итерация 3)

См. также

• H-дерево
• Кривая заполнения пространства
• Быстрое исследование случайного дерева (RRT)
• Разделение двоичного пространства