H 트리

H tree
Linux 파일 시스템 색인 구조인 HTree와 혼동하지 마십시오.
H 트리의 처음 10단계는

프랙탈 기하학에서 H 트리는 수직선 세그먼트로 구성된 프랙탈 트리 구조이며, 각각은 다음으로 큰 인접 세그먼트로부터의 제곱근 2의 배수로 작다.이것은 반복되는 패턴이 문자 "H"를 닮았다고 해서 그렇게 불립니다.하우스도르프 치수 2를 가지며 직사각형 내의 모든 점에 임의로 근접합니다.응용분야는 VLSI 설계와 마이크로파 엔지니어링이다.

건설

한 H나무 길이의 선 세그먼트로 그것의 끝점들을 통해 첫번째에 대해서 직각이며, 같은 맥락에서 계속되는 두개의 짧은 세그먼트를 그리기, 선 세그먼트를 각 단계에서 2{\displaystyle{\sqrt{2}에 의해}}의( 나누)은 길이를 줄이는 것은 이 건축 사의 변형 .[1]시작으로 생성할 수 있uld또한 각 반복의 길이에 1/ 1 의 비율을 곱하는 것으로 정의되지만, 이 변형에서는 결과 형상이 프랙탈 [2]경계가 있는 경계 직사각형의 일부만을 커버합니다.

같은 프랙탈세트를 생성하는 대체 공정은 1 1의 비율로 변이 있는 직사각형에서 시작하여 두 개의 작은 은색 직사각형으로 반복적으로 이등분하는 것이다.다른 형상의 직사각형에서도 유사한 프로세스를 수행할 수 있지만 1 1 직사각형의 각 단계에서 크기가 2displaystyle {2 균일하게 감소하지만 다른 직사각형의 경우 홀수 수준과 균등하게 감소합니다.recursive construction의 ls.

특성.

H 트리는 자기 유사 프랙탈이며 하우스도르프 치수는 [2]2입니다.

H 트리의 점은 직사각형의 모든 점에 임의로 근접합니다(분할된 직사각형의 중심별 구성의 시작 직사각형과 동일).그러나 직사각형의 모든 점을 포함하는 것은 아닙니다. 예를 들어 초기 선분의 수직 이등분선상의 점(이 세그먼트의 중간점 제외)은 포함되지 않습니다.

적용들

VLSI 설계에서 H 트리는 [3]트리의 노드 수에 비례하는 총 면적을 사용하여 완전한 이진 트리의 레이아웃으로 사용될 수 있습니다.또, H트리는, 그래프 [4]그리기에서의 수목의 공간 효율이 높은 레이아웃을 형성해, 여행 세일즈맨 투어의 엣지 길이의 제곱합이 [5]큰 점 세트의 구성중의 일부로서 구성된다.일반적으로 각 부품에 [6]동일한 전파 지연을 가진 칩의 모든 부분에 타이밍 신호를 라우팅하기 위한 클럭 분배 네트워크로 사용되며 VLSI 멀티프로세서의 [7]상호 연결 네트워크로도 사용됩니다.

3차원 H 트리

평면 H 트리는 H 트리 [8]평면에 수직인 방향으로 선분을 추가하여 3차원 구조로 일반화할 수 있습니다.결과적인 3차원 H 트리는 하우스도르프 치수가 3과 같다.평면 H 트리와 그 3차원 버전은 광결정과 메타물질에서 인공 전자기 원자를 구성하는 것으로 밝혀졌으며 마이크로파 [8]공학에서 잠재적으로 응용될 수 있다.

관련 세트

H 트리보다 날카로운 각도로 프랙탈 캐노피를 스스로 겹침

H 트리는 인접 선분 사이의 각도가 항상 180도인 프랙탈 캐노피의 예입니다.경계 직사각형의 모든 점에 임의로 근접하는 특성으로, 공간 채우기 곡선과 유사하지만, 그 자체는 곡선이 아닙니다.

위상적으로 H 트리는 덴드로이드와 유사한 특성을 가지고 있습니다.그러나 덴드로이드는 덴드로이드가 아닙니다. 덴드로이드는 닫힌 집합이어야 하며 H 트리는 닫히지 않습니다(닫힘이 전체 직사각형임).

H 트리의 선분 대신 굵어진 다각형 가지가 있는 동일한 트리 구조의 변화는 Benoit Mandelbrot에 의해 정의되었으며, 때때로 Mandelbrot 트리라고 불립니다.이러한 변형에서 나무의 잎과 굵어진 가지 사이에 겹치지 않도록 각 수준에서 크기를 줄이는 스케일 팩터는 2보다 약간 커야 합니다[9]

메모들

  1. ^ 라우베리에(1991), 페이지 1-2.
  2. ^ a b Kaloshin & Saprykina (2012).
  3. ^ Leiserson(1980).
  4. ^ Nguyen & Huang (2002).
  5. ^ Bern & Eppstein (1993)
  6. ^ 울만(1984년); 부르키스(1991년).
  7. ^ 브라우닝(1980).특히 그림 1.1.5 (15페이지)를 참조하십시오.
  8. ^ a b 후 등 (2008년);Wen 등 (2002).
  9. ^ 라우베리에(1991), 페이지 71-73.

레퍼런스

  • 를 클릭합니다Bern, Marshall; Eppstein, David (1993), "Worst-case bounds for subadditive geometric graphs", Proc. 9th Annual Symposium on Computational Geometry (PDF), Association for Computing Machinery, pp. 183–188, doi:10.1145/160985.161018.
  • 를 클릭합니다Browning, Sally A. (1980), The Tree Machine: A Highly Concurrent Computing Environment, Ph.D. thesis, California Institute of Technology.
  • 를 클릭합니다Burkis, J. (1991), "Clock tree synthesis for high performance ASICs", IEEE International Conference on ASIC, pp. 9.8.1–9.8.4, doi:10.1109/ASIC.1991.242921.
  • 를 클릭합니다Hou, Bo; Xie, Hang; Wen, Weijia; Sheng, Ping (2008), "Three-dimensional metallic fractals and their photonic crystal characteristics" (PDF), Physical Review B, 77 (12): 125113, doi:10.1103/PhysRevB.77.125113.
  • 를 클릭합니다Kaloshin, Vadim; Saprykina, Maria (2012), "An example of a nearly integrable Hamiltonian system with a trajectory dense in a set of maximal Hausdorff dimension", Communications in Mathematical Physics, 315 (3): 643–697, doi:10.1007/s00220-012-1532-x, MR 2981810.
  • Lauwerier, Hans (1991), Fractals: Endlessly Repeated Geometrical Figures, Princeton Science Library, vol. 6, translated by Gill-Hoffstadt, Sophia, Princeton University Press, ISBN 9780691024455
  • 를 클릭합니다Leiserson, Charles E. (1980), "Area-efficient graph layouts", 21st Annual Symposium on Foundations of Computer Science (FOCS 1980), pp. 270–281, doi:10.1109/SFCS.1980.13.
  • 를 클릭합니다Nguyen, Quang Vinh; Huang, Mao Lin (2002), "A space-optimized tree visualization", IEEE Symposium on Information Visualization, pp. 85–92, doi:10.1109/INFVIS.2002.1173152.
  • 를 클릭합니다Ullman, Jeffrey D. (1984), Computational Aspects of VSLI, Computer Science Press.
  • 를 클릭합니다Wen, Weijia; Zhou, Lei; Li, Jensen; Ge, Weikun; Chan, C. T.; Sheng, Ping (2002), "Subwavelength photonic band gaps from planar fractals" (PDF), Physical Review Letters, 89 (22): 223901, doi:10.1103/PhysRevLett.89.223901, PMID 12485068.