kdtree
クラス · 二次元kd-tree
struct kdtree;
概要
二次元kd-tree
点の追加後に build() し、最近点距離と半開矩形内の点IDを検索する。
計算量
- 構築は $O(n\log^2 n)$。検索は平均 $O(\sqrt n+k)$、 最悪 $O(n)$（$k$ は報告点数）
構築・破棄
| 名前 | 説明 | 計算量 |
|---|---|---|
(constructor) |
空の kd-tree を作る | $O(1)$ |
メンバ関数
| 名前 | 説明 | 計算量 |
|---|---|---|
add |
点 (x, y) を追加し、追加順の ID を割り当てる |
償却 $O(1)$ |
build |
追加済みの点から kd-tree を構築する | $O(n\log^2 n)$ |
find |
(1) 点 (x, y) から最近点までの距離の二乗を返す(2) 半開矩形 $[sx,tx)\times[sy,ty)$ 内にある点の ID を返す |
(1) 平均 $O(\sqrt n)$、最悪 $O(n)$ (2) 平均 $O(\sqrt n+k)$、最悪 $O(n)$（ k は返す点数） |
メンバの詳細
find
// (1)
std::int64_t find(int x, int y);
// (2)
std::vector<int> find(int sx, int tx, int sy, int ty);
(1) 点 (x, y) から最近点までの距離の二乗を返す
- 計算量: 平均 $O(\sqrt n)$、最悪 $O(n)$
(2) 半開矩形 $[sx,tx)\times[sy,ty)$ 内にある点の ID を返す
- 計算量: 平均 $O(\sqrt n+k)$、最悪 $O(n)$（
kは返す点数）