「K-d木」の版間の差分
ナビゲーションに移動
検索に移動
Albeit-Kun (トーク | 投稿記録) |
|||
| (3人の利用者による、間の3版が非表示) | |||
| 1行目: | 1行目: | ||
| − | '''【けいでぃーき ( | + | '''【けいでぃーき (<math>k-d \,</math> tree)】''' |
| + | 与えられた点集合に基づいて <math>k \,</math>次元の空間の領域分割を表現するデータ構造である. 根に全体領域が対応し, その左右の子には第1座標に注目して左右に二等分された点集合の領域が対応する. 次に分割された左(右)点集合領域を第2座標に基づいて上下に二等分しそれぞれ左(右)の子の左右の子に対応させる. 以下同様に分割し, 領域に点が1個になったら分割を終了する. この分割法を表現したものが <math>k \,</math>-<math>d \,</math>木である. | ||
| − | + | [[Category:計算幾何|けいでぃーき]] | |
2008年11月5日 (水) 16:40時点における最新版
【けいでぃーき ( tree)】
与えられた点集合に基づいて 次元の空間の領域分割を表現するデータ構造である. 根に全体領域が対応し, その左右の子には第1座標に注目して左右に二等分された点集合の領域が対応する. 次に分割された左(右)点集合領域を第2座標に基づいて上下に二等分しそれぞれ左(右)の子の左右の子に対応させる. 以下同様に分割し, 領域に点が1個になったら分割を終了する. この分割法を表現したものが -木である.
