OR事典

K-d木

読み方：けいでぃーき
【英】：tree

与えられた点集合に基づいて 次元の空間の領域分割を表現するデータ構造である. 根に全体領域が対応し, その左右の子には第1座標に注目して左右に二等分された点集合の領域が対応する. 次に分割された左(右)点集合領域を第2座標に基づいて上下に二等分しそれぞれ左(右)の子の左右の子に対応させる. 以下同様に分割し, 領域に点が1個になったら分割を終了する. この分割法を表現したものが -木である.

「OR事典」の他の用語

計算幾何：

K-d木  NP困難  TSP多面体  アレンジメント  ガブリエルグラフ  スケルトン  スラブ法