「K-d木」の版間の差分
ナビゲーションに移動
検索に移動
| 1行目: | 1行目: | ||
'''【けいでぃーき (<math>k-d \,</math> tree)】''' | '''【けいでぃーき (<math>k-d \,</math> tree)】''' | ||
| − | |||
与えられた点集合に基づいて <math>k \,</math>次元の空間の領域分割を表現するデータ構造である. 根に全体領域が対応し, その左右の子には第1座標に注目して左右に二等分された点集合の領域が対応する. 次に分割された左(右)点集合領域を第2座標に基づいて上下に二等分しそれぞれ左(右)の子の左右の子に対応させる. 以下同様に分割し, 領域に点が1個になったら分割を終了する. この分割法を表現したものが <math>k \,</math>-<math>d \,</math>木である. | 与えられた点集合に基づいて <math>k \,</math>次元の空間の領域分割を表現するデータ構造である. 根に全体領域が対応し, その左右の子には第1座標に注目して左右に二等分された点集合の領域が対応する. 次に分割された左(右)点集合領域を第2座標に基づいて上下に二等分しそれぞれ左(右)の子の左右の子に対応させる. 以下同様に分割し, 領域に点が1個になったら分割を終了する. この分割法を表現したものが <math>k \,</math>-<math>d \,</math>木である. | ||
2007年7月16日 (月) 15:37時点における版
【けいでぃーき ( tree)】
与えられた点集合に基づいて 次元の空間の領域分割を表現するデータ構造である. 根に全体領域が対応し, その左右の子には第1座標に注目して左右に二等分された点集合の領域が対応する. 次に分割された左(右)点集合領域を第2座標に基づいて上下に二等分しそれぞれ左(右)の子の左右の子に対応させる. 以下同様に分割し, 領域に点が1個になったら分割を終了する. この分割法を表現したものが -木である.
