Difference between revisions of "Kd-tree"
(create stub) |
m (Minor grammar fixes) |
||
| Line 2: | Line 2: | ||
In [[wikipedia:computer science|computer science]], a '''kd-tree''' (short for ''k''-dimensional tree) is a [[wikipedia:space-partitioning|space-partitioning]] [[wikipedia:data structure|data structure]] for organizing points in a k-dimensional space. kd-trees are a useful data structure for several applications, such as searches involving a multidimensional search key (e.g. range searches and [[wikipedia:nearest neighbor search|nearest neighbour searches]]). kd-trees are a special case of [[wikipedia:BSP tree|BSP trees]]. | In [[wikipedia:computer science|computer science]], a '''kd-tree''' (short for ''k''-dimensional tree) is a [[wikipedia:space-partitioning|space-partitioning]] [[wikipedia:data structure|data structure]] for organizing points in a k-dimensional space. kd-trees are a useful data structure for several applications, such as searches involving a multidimensional search key (e.g. range searches and [[wikipedia:nearest neighbor search|nearest neighbour searches]]). kd-trees are a special case of [[wikipedia:BSP tree|BSP trees]]. | ||
| − | In [[Robocode]], a '''kd-tree''' is a data structure use for ''k''-nearest neighbours searching in [[Dynamic Clustering]] data logging | + | In [[Robocode]], a '''kd-tree''' is a data structure use for ''k''-nearest neighbours searching in [[Dynamic Clustering]] data logging algorithms. Currently, the most popular type of kd-tree in Robocode is the Bucket PR kd-tree. |
== How it works? == | == How it works? == | ||
| Line 11: | Line 11: | ||
== Implementations == | == Implementations == | ||
| − | There are several implementation of kd-tree around today, most if not all of them are bucket PR kd-trees: | + | There are several implementation of kd-tree around today, and most if not all of them are bucket PR kd-trees: |
* [[User:Rednaxela/kD-Tree|Rednaxela's kd-tree]]: The fastest and most efficient kd-tree around today. | * [[User:Rednaxela/kD-Tree|Rednaxela's kd-tree]]: The fastest and most efficient kd-tree around today. | ||
* [[Diamond/Code|Voidious's kd-tree]]: The second-to-top tree. | * [[Diamond/Code|Voidious's kd-tree]]: The second-to-top tree. | ||
Revision as of 16:56, 29 August 2009
| This article is a stub. You can help RoboWiki by expanding it. |
In computer science, a kd-tree (short for k-dimensional tree) is a space-partitioning data structure for organizing points in a k-dimensional space. kd-trees are a useful data structure for several applications, such as searches involving a multidimensional search key (e.g. range searches and nearest neighbour searches). kd-trees are a special case of BSP trees.
In Robocode, a kd-tree is a data structure use for k-nearest neighbours searching in Dynamic Clustering data logging algorithms. Currently, the most popular type of kd-tree in Robocode is the Bucket PR kd-tree.
How it works?
Please complete this section if you can (about real kd-tree, not bucket PR kd-tree)
Bucket PR kd-tree
Please complete this section if you can
Implementations
There are several implementation of kd-tree around today, and most if not all of them are bucket PR kd-trees:
- Rednaxela's kd-tree: The fastest and most efficient kd-tree around today.
- Voidious's kd-tree: The second-to-top tree.
- Simonton's kd-tree: The first bucket PR kd-tree in Robocode community.
