공간을 채우는 나무

공간을 채우는 나무는 공간을 채우는 곡선과 유사하지만 ^[1]나뭇가지와 나무와 같은 구조로 뿌리를 내리고 있는 기하학적 구조물이다.공간을 채우는 트리는 공간의 모든 지점이 그것에 수렴되는 유한한 길이의 경로를 갖는 트리를 생성하는 증분 프로세스에 의해 정의된다.공간을 채우는 곡선과 대조적으로 나무의 개별 경로는 짧아서 공간의 어떤 부분도 뿌리부터 빠르게 도달할 수 있다.^[2]^[3] 공간을 채우는 나무의 가장 단순한 예는 규칙적이고, 자기 유사하며, 프랙탈 구조를 가지고 있지만, 비정규적이고 심지어 무작위화된/몬테 카를로 변형으로 일반화할 수 있다(임의의 나무를 빠르게 탐사하는 방법 참조).공간을 채우는 나무는 유체 분배 시스템, 혈관 네트워크, 프랙탈 식물 성장 등 자연에서 흥미로운 유사점을 가지고 있으며, 컴퓨터 과학에서 L-시스템과의 흥미로운 연결이 많다.

정의

공간을 채우는 나무는 연속적인 공간에 있는 한 점을 통해 한정된 길이의 경로에 의해 공간의 다른 모든 지점에 연속적인 경로를 통해 연결되며, 공간의 모든 지점에 대해 적어도 한 개의 경로가 수렴되는 반복적인 프로세스에 의해 정의된다.

이런 의미에서 '공간 채우기 나무'라는 용어는 수학에서 기존의 정의와 달리 '공간 채우기'와 '나무'를 다르게 정의한 2009년 기술 보고서에서 만들어졌다.공간 채우기 곡선 기사에서 설명했듯이 1890년 페아노는 최초의 공간 채우기 곡선을 발견했고, 현재 표준화된 요르단의 1887년 정의에 따르면 곡선은 함수의 순서가 아니라 하나의 함수다.곡선은 "범위가 2차원 단위 사각형 전체를 포함하는 곡선"이기 때문에 "공간 충만"이다(공간 충만 곡선의 첫 문장에서 설명).

이와는 대조적으로, 기술 보고서에 정의된 대로 공간을 채우는 트리는 하나의 트리가 아니다.그것은 단지 일련의 나무일 뿐이다.이 논문은 "공간을 채우는 나무는 사실 무한히 연속된 나무로 정의된다"고 말한다. $T_{\text{square}}$ $T_{\text{square}}$ ${\$ 을(를) "나무의 순서"로 $T_{\text{square}}$ 정의한 다음 " $T_{\text{square}}$ $T_{\text{square}}$ ${\$ 는) 공간을 채우는 나무"라고 $T_{\text{square}}$ 명시한다.2차원 단위 사각형 전체를 포함한다는 표준적 의미에서는 공간을 채우는 것이 아니다.대신에, 논문은 그것을 임의로 모든 점들에 가까이 오는 순서에 있는 나무들을 갖는 것으로 정의한다."각 x t X에 대해 나무의 뿌리에서 시작하여 x로 수렴하는 경로가 존재한다면, 나무 시퀀스 T는 공간 X에서 '공간 충만'이라고 한다."고 명시되어 있다.이 개념의 표준 용어는 단위 광장의 모든 곳에 밀집된 점 집합을 포함한다는 것이다.

예

공간을 채우는 나무의 가장 간단한 예는 사각 평면 영역을 채우는 것이다.이미지는 평면 영역 $[0,1]^{2}\subset \mathbb {R} ^{2}$ $[0,1]^{2}\subset \mathbb {R} ^{2}$ $[0,1]^{2}\subset \mathbb {R} ^{2}$ $[0,1]^{2}\subset \mathbb {R} ^{2}$ $[0,1]^{2}\subset \mathbb {R} ^{2}$ $[0,1]^{2}\subset \mathbb {R} ^{2}$ $[0,1]^{2}\subset \mathbb {R} ^{2}$ $[0,1]^{2}\subset \mathbb {R} ^{2}$ ${\$ 회 반복할 때마다 기존 나무에 가지를 추가한다 $[0,1]^{2}\subset \mathbb {R} ^{2}$

정사각형 공간 채우기 트리(이행 1)
정사각형 공간 채우기 트리(이행 2)
정사각형 공간 채우기 트리(이중 3)
정사각형 공간 채우기 트리(이행렬
정사각형 공간 채우기 트리(이행 5)
정사각형 공간 채우기 트리(이행 6)

공간을 채우는 나무는 다양한 다른 모양과 볼륨에 대해 정의될 수 있다.아래는 삼각형 영역에 대한 공간 채우기를 정의하는 데 사용되는 분할 체계다.반복할 때마다 각 삼각형의 중심과 4개의 하위 삼각형의 중심을 연결하는 기존 나무에 가지를 추가한다.

삼각형 공간 채우기 트리의 처음 3회 반복에 대한 분할 계획

삼각형 공간을 채우는 트리의 처음 6번 반복은 다음과 같다.

삼각형 공간 채우기 트리(이중 1)
삼각형 공간 채우기 트리(이중 2)
삼각형 공간 채우기 트리(이중 3)
삼각형 공간 채우기 트리(이중 4)
삼각형 공간 채우기 트리(이중 5)
삼각형 공간 채우기 트리(이중 6)

공간을 채우는 나무도 더 높은 차원으로 건설될 수 있다.가장 간단한 $\mathbb {R} ^{3}$ 로는 R $\mathbb {R} ^{3}$ ${\$ ^{ $3}$ 의 큐브와 $\mathbb {R} ^{3}$ $\mathbb {R} ^{n}$ $\mathbb {R} ^{n}$ ${\$ ^{ $n}}}$ 의 하이퍼큐브가 있으며 $\mathbb {R} ^{n}$ 사각공간 채우기 트리에 사용되는 유사한 반복 순서도 하이퍼큐브에 사용할 수 있다. $\mathbb {R} ^{3}$ $\mathbb {R} ^{3}$ ${\$ 에서 이러한 공간을 채우는 트리의 세 번째 반복은 다음과 $\mathbb {R} ^{3}$ 같다.

큐브 공간 채우기 트리(이중 3)

참고 항목

참조

^ Sagan, H., J. Holbrook: "공간 채우기 곡선", Springer-Verlag, 1994, 뉴욕
^ Kuffner, J. J., S. M. LaValle: The Robotics Institute, Carnegie Mellon University, CMU-RI-TR-09-47, 2009.
^ 커프너(Kuffner), 라발레(LaValle), S.M. "공간을 채우는 나무:운동 계획의 증분 검색에 대한 새로운 관점," 지능형 로봇 및 시스템 (IROS), 2011 IEEE/RSJ 국제 회의 , vol, no, pp.2199-2206, 25-30
^ Kuffner, J. J., S. M. LaValle: The Robotics Institute, Carnegie Mellon University, CMU-RI-TR-09-47, 2009.

[1] Sagan, H., J. Holbrook: "공간 채우기 곡선", Springer-Verlag, 1994, 뉴욕

[2] Kuffner, J. J., S. M. LaValle: The Robotics Institute, Carnegie Mellon University, CMU-RI-TR-09-47, 2009.

[3] 커프너(Kuffner), 라발레(LaValle), S.M. "공간을 채우는 나무:운동 계획의 증분 검색에 대한 새로운 관점," 지능형 로봇 및 시스템 (IROS), 2011 IEEE/RSJ 국제 회의 , vol, no, pp.2199-2206, 25-30

[4] Kuffner, J. J., S. M. LaValle: The Robotics Institute, Carnegie Mellon University, CMU-RI-TR-09-47, 2009.

[1]

[2]

[3]

Search

공간을 채우는 나무

네임스페이스

더

목차

정의

예

참고 항목

참조