FMM (Fast Multipole Method)의 대부분 (모두?) 구현에서 octree는 관련 도메인을 분해하는 데 사용됩니다. 이론적으로 octree는 간단한 체적 경계를 제공하며, 이는 FMM의 O (n) 런타임을 증명하는 데 유용합니다. 이 이론적 근거를 넘어서 다른 트리 또는 트리 데이터 구조보다 Octree를 사용하면 이점이 있습니까?
셀이 바로 인접한 이웃을 알기 때문에 octree를 사용하면 상호 작용 목록을 쉽게 결정할 수 있습니다. 그러나 Dual Tree Traversal 과 같은보다 동적 인 트리 탐색을 사용하면 상호 작용 목록이 필요하지 않습니다.
대안은 kd-tree입니다. 이론적 인 단점 중 하나는 건설에 값 비싼 평균 찾기 작업이 필요하다는 것입니다. 그러나 공간 분할이 덜 효율적이지만 건설 중에 중간 값을 찾을 필요가없는 kd-tree 버전이 있습니다. 구현 측면에서 kd-tree는 매우 간단합니다.
훨씬 더 근본적인 대안은 R-tree 일 수 있습니다 .
그래서 제 질문은 FMM을위한 최고의 선택을하는 Octrees는 무엇입니까?
답변
위의 설명은 옥트리를 사용하는 몇 가지 좋은 이유를 제시합니다 (즉, 보다 일반적인 직교 이분법과는 달리 각 차원에서 계산 큐브를 반복적 으로 반으로 줄임 ). 상호 작용 목록 계산의 대칭과 단순성은 큰 장점입니다.
Otree가 테이블에 가져 오는 가장 중요한 기능은 FMM을 인수하는 추가 정리 가 하나 이상의 “버퍼”라는 매우 간단한 분리 기준으로 형상과 상관없이 원거리 상호 작용에 대해 체계적으로 만족 된다는 것 입니다. 상자. 다시 말해서, 잠재적 필드의 FMM 합계 표현은 비 병리 적 상황에서 질서가 증가함에 따라 수렴된다는 것이 보장된다.