Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
k-d tree
open-in-new
Wikimedia Commons has media related to k-d trees. <p>In <a href="/facts/Computer_science/lN3pEyPz">computer science</a>, a <i>k</i>-d tree (short for <i>k-dimensional <a href="/facts/Tree_data_structure/RcXz9noF">tree</a></i>) is a <a href="/facts/Space_partitioning/znppkQCM">space-partitioning</a> <a href="/facts/Data_structure/yNsNvL1I">data structure</a> for organizing <a href="/facts/Point_(geometry)/6YPAvX2a">points</a> in a <i>k</i>-dimensional <a href="/facts/Euclidean_space/R2UbzmzM">space</a>. K-dimensional is that which concerns exactly k orthogonal axes or a space of any number of <a href="/facts/Dimension/0ktmUyac">dimensions</a>. <i>k</i>-d trees are a useful data structure for several applications, such as: </p> <ul><li>Searches involving a multidimensional search key (e.g. <a href="/facts/Range_search/Fkls9MD3">range searches</a> and <a href="/facts/Nearest_neighbor_search/R6QTyAph">nearest neighbor searches</a>) &</li> <li>Creating <a href="/facts/Point_cloud/dN8eG4AU">point clouds</a>.</li></ul> <p><i>k</i>-d trees are a special case of <a href="/facts/Binary_space_partitioning/sn9MhTSB">binary space partitioning</a> trees. </p>