「Kd木」の版間の差分

''k''d木は高次元空間での最近傍探索には適さない。次元を ''D'' としたとき、点の個数 ''N'' は ''N >> 2^D'' となっているのが望ましい。そうでないと、高次元データを''k''d木で表すと、最近傍探索でほとんどの点を調べることになり、[[力まかせ探索]]とあまり差がない。高次元データでの最近傍探索問題は[[NP困難]]問題と似ていると考えられている<ref>Piotr Indyk. Nearest neighbors in high-dimensional spaces. Handbook of Discrete and Computational Geometry, chapter 39. Editors: Jacob E. Goodman and Joseph O'Rourke, CRC Press, 2nd edition, 2004.</ref>。そのため近似最近傍探索の手法が使われることが多い。