어떤 상황에서 K-D tree를 사용하기 좋을까요? 반대로, 어떤 상황에서 Octree를 사용하기 좋을까요?

이 게시글은 장형기님의 SLAM 기술면접 질문 100선에 대한 제 나름대로의 답을 정리한 것입니다.

K-D tree와 Octree에 대해 알아보았습니다. 이 게시글에서 각자 어느 분야에서 사용해야하는지 알아보겠습니다.

K-D tree를 사용하기 좋은 상황

• 저차원 공간 데이터(2D, 3D)

  • K-D tree는 저차원 공간에서 효율적이고 주로 10차원 이하의 데이터에서 활용됩니다.
    LIO-SAM이나 LOAM 같은 LiDAR SLAM의 경우 point cloud를 k-d tree로 관리합니다.
    
    

• Nearest Neighbor Search

  • K-D tree는 공간 내에서 특정 점에 가까운 데이터를 효율적으로 찾는데 적합합니다.
    Knn Search나 radius Search가 효율적입니다.
    
    

• 균형 잡힌 데이터 분포

  • 데이터가 비교적 균일하게 분포된 경우, K-D 트리는 균형 잡힌 구조를 유지하여 효율적인 검색을 제공합니다.
  
  

• 정적 데이터 집합
  데이터가 주로 읽기 전용이거나, 갱신이 거의 없는 경우에 적합합니다.
  계속 데이터를 삽입하거나 제거해야하는 경우 트리를 재구성해야하기 때문에 연산량이 많아질 수 있습니다.

  Octree를 사용하기 좋은 상황

• 3차원 공간 데이터

  • Octree는 3D 공간에서 데이터를 관리하기 위해 설계되어있습니다. 자세한건 이전 게시글에서 확인하면 좋을 것 같습니다.
  
  

• 공간 점유 정보 관리

  • 옥트리는 공간을 효율적으로 분할하여 점유 여부를 나타낼 때 적합합니다.
  
  

• 비균형 데이터 분포

  • 데이터가 특정 공간에 몰려 있는 경우, 옥트리는 해당 영역만 더 세분화하기 때문에 효율적으로 공간을 분할할 수 있습니다.
    
    

• 동적인 데이터

  • Octree는 데이터가 동적으로 변경되거나, 삽입/삭제가 빈번한 경우에도 적합합니다.

  ---

  3D reconstruction 기법을 쓰는 SLAM의 경우 Octree를 많이 사용하고 그냥 LiDAR SLAM은 K-D tree를 사용하는 것 같습니다. Octree는 공간이 한정적이기 때문에 scale이 큰 경우는 K-D tree를 사용하는 것 같은데 관리는 Octree가 쉬워서 선택을 잘 해야할 것 같습니다.