Ball-Tree

• 相对KD-Tree
  • 新点与边界距离变大
    • 时间复杂度
      • 最快${\log }_{2}N$
      • 最慢N
        • 但相比KD-Tree概率变小
  • 建树开销大
• 实现
  • 一开始一个球
    • 球内找两个相距最远点
    • 遍历其它点与两点距离，成两部分
    • 每部分找圆心
      • 找x,y平均值为圆心
      • 圆心与每个点算r, 求max(r1,r2,…,rn)
    • 每部分再划分
• 划分步骤
  • 新点P为圆心，P所在区域r为半径，判断与其它圆是否交集
    • $\Vert P,A\Vert <r_1+r_2$, A是其它圆心