In computer science, a '''''k''d-tree''' (short for ''k-dimensional tree data structure'') is a space partitioning data structure for organizing points in a ''k''-dimensional Euclidean space. ''k''d-trees are a special case of BSP trees. A ''k''d-tree uses only splitting planes that are perpendicular to one of the coordinate system axes. This differs from BSP trees, in which arbitrary splitting planes can be used. In addition, every node (computer science) of a ''k''d-tree, from the root node to the leaf node, stores a point. This differs from BSP trees, in which leaves are typically the only nodes that contain points (or other geometric primitive (geometry)). As a consequence, each splitting plane must go through one of the points in the ''k''d-tree. Technically, the letter ''k'' refers to the number of dimensions. A 3-dimensional ''k''d-tree would be called a 3d-tree. However, the phrase "3-dimensional ''k''d-tree" is more commonly used. (It is also more descriptive, since a 3-dimensional tree could be any of a variety of different things, but the term ''k''d-tree refers to a specific type of space-partitioning tree.) The letters ''k'' and d are both lowercase, even when the term comes at the beginning of a sentence, and the ''k'' is in ''italics''. However, variant spellings are common, such as KD-tree and Kd-tree. ==Operations on ''k''d-trees== ===Constructing a ''k''d-tree=== Since there are many possible ways to choose axis-aligned splitting planes, there are many different ways to construct ''k''d-trees. The canonical method of ''k''d-tree construction has the following constraints: * As one moves down the tree, one cycles through the axes used to select the splitting planes. (For example, the root would have an ''x''-aligned plane, the root's children would both have ''y''-aligned planes, the root's grandchildren would all have ''z''-aligned planes, and so on.) * At each step, the point selected to create the splitting plane is the median of the points being put into the ''k''d-tree, with respect to their coordinates in the axis being used. This method leads to a balanced tree ''k''d-tree, in which each leaf node is about the same distance from the root. However, balanced trees are not necessarily optimal for all applications. Given a list of ''n'' points, the following algorithm will construct a balanced ''k''d-tree containing those points. function kdtree (''list of points'' pointList, ''int'' depth) { if pointList is empty return nil; else { ''// Select axis based on depth so that axis cycles through all valid values'' var ''int'' axis := depth mod k; ''// Sort point list and choose median as pivot element'' sort pointList using predicate: point1[axis] < point2[axis]; choose median from pointList; ''// Create node and construct subtrees'' var ''tree_node'' node; node.location := median; node.leftChild := kdtree(points in pointList before median, depth+1); node.rightChild := kdtree(points in pointList after median, depth+1); return node; } } This algorithm creates the invariant (computer science) that for any node, all the nodes in the left subtree are on one side of a splitting plane (mathematics), and all the nodes in the right subtree are on the other side. The splitting plane of a node goes through the point associated with that node (referred to in the code as ''node.location''). ===Adding elements to a ''k''d-tree=== One adds a new point to a ''k''d-tree in the same way as one adds an element to any other tree. First, traverse the tree, starting from the root and moving to either the left or the right child depending on whether the point to be inserted is on the "left" or "right" side of the splitting plane. Once you get to a leaf node, add the new point as either the left or right child of the leaf node, again depending on which side of the node's splitting plane contains the new point. ===Removing elements from a ''k''d-tree=== Remove a point from an existing ''k''d-tree, without breaking the invariant. (Undone) ===Balancing a ''k''d-tree=== Balancing a ''k''d-tree requires care. Because ''k''d-trees are sorted in multiple dimensions, the tree rotation technique cannot be used to balance them — this may break the invariant. ==Uses for ''k''d-trees== ===Orthogonal range search in a ''k''d-tree=== Use a ''k''d-tree to find all the points that lie within a given rectangle (or higher-dimensional region analogous to a rectangle). This operation is also called an orthogonal range search. (Undone) ===Determining where to evaluate a surface=== In local regression, it is common to evaluate the fitted surface directly only at the vertices of a ''k''d-tree and to interpolate elsewhere. This use, which is pictured in the image above, is to ensure that only as many direct evaluations are performed as are necessary. Since the ''k''d-tree "adapts" itself to the space of predictor variables, this method can provide an excellent approximation to the true local regression surface. If the approximation is poor, it can be improved by further subdivision of the tree's cells. ==Complexity== * Building a static ''k''d-tree from ''n'' points takes Big O notation(''n'' log ''n'') time. * Inserting a new point into a balanced ''k''d-tree takes O(log ''n'') time. * Removing a point from a balanced ''k''d-tree takes O(log ''n'') time. ==External links== * [http://www.rolemaker.dk/nonRoleMaker/uni/algogem/kdtree.htm Java applet demonstrating 2-dimensional ''k''d-trees] Computer science Computer graphics Trees (structure)
See other meanings of words starting from letter:
Words begining with Kd-tree:
Kd-tree
Kd-tree
In computer science, a '''''k''d-tree''' (short for ''k-dimensional tree data structure'') is a space partitioning data structure for organizing points in a ''k''-dimensional Euclidean space. ''k''d-trees are a special case of BSP trees. A ''k''d-tree uses only splitting planes that are perpendicular to one of the coordinate system axes. This differs from BSP trees, in which arbitrary splitting planes can be used. In addition, every node (computer science) of a ''k''d-tree, from the root node to the leaf node, stores a point. This differs from BSP trees, in which leaves are typically the only nodes that contain points (or other geometric primitive (geometry)). As a consequence, each splitting plane must go through one of the points in the ''k''d-tree. Technically, the letter ''k'' refers to the number of dimensions. A 3-dimensional ''k''d-tree would be called a 3d-tree. However, the phrase "3-dimensional ''k''d-tree" is more commonly used. (It is also more descriptive, since a 3-dimensional tree could be any of a variety of different things, but the term ''k''d-tree refers to a specific type of space-partitioning tree.) The letters ''k'' and d are both lowercase, even when the term comes at the beginning of a sentence, and the ''k'' is in ''italics''. However, variant spellings are common, such as KD-tree and Kd-tree. ==Operations on ''k''d-trees== ===Constructing a ''k''d-tree=== Since there are many possible ways to choose axis-aligned splitting planes, there are many different ways to construct ''k''d-trees. The canonical method of ''k''d-tree construction has the following constraints: * As one moves down the tree, one cycles through the axes used to select the splitting planes. (For example, the root would have an ''x''-aligned plane, the root's children would both have ''y''-aligned planes, the root's grandchildren would all have ''z''-aligned planes, and so on.) * At each step, the point selected to create the splitting plane is the median of the points being put into the ''k''d-tree, with respect to their coordinates in the axis being used. This method leads to a balanced tree ''k''d-tree, in which each leaf node is about the same distance from the root. However, balanced trees are not necessarily optimal for all applications. Given a list of ''n'' points, the following algorithm will construct a balanced ''k''d-tree containing those points. function kdtree (''list of points'' pointList, ''int'' depth) { if pointList is empty return nil; else { ''// Select axis based on depth so that axis cycles through all valid values'' var ''int'' axis := depth mod k; ''// Sort point list and choose median as pivot element'' sort pointList using predicate: point1[axis] < point2[axis]; choose median from pointList; ''// Create node and construct subtrees'' var ''tree_node'' node; node.location := median; node.leftChild := kdtree(points in pointList before median, depth+1); node.rightChild := kdtree(points in pointList after median, depth+1); return node; } } This algorithm creates the invariant (computer science) that for any node, all the nodes in the left subtree are on one side of a splitting plane (mathematics), and all the nodes in the right subtree are on the other side. The splitting plane of a node goes through the point associated with that node (referred to in the code as ''node.location''). ===Adding elements to a ''k''d-tree=== One adds a new point to a ''k''d-tree in the same way as one adds an element to any other tree. First, traverse the tree, starting from the root and moving to either the left or the right child depending on whether the point to be inserted is on the "left" or "right" side of the splitting plane. Once you get to a leaf node, add the new point as either the left or right child of the leaf node, again depending on which side of the node's splitting plane contains the new point. ===Removing elements from a ''k''d-tree=== Remove a point from an existing ''k''d-tree, without breaking the invariant. (Undone) ===Balancing a ''k''d-tree=== Balancing a ''k''d-tree requires care. Because ''k''d-trees are sorted in multiple dimensions, the tree rotation technique cannot be used to balance them — this may break the invariant. ==Uses for ''k''d-trees== ===Orthogonal range search in a ''k''d-tree=== Use a ''k''d-tree to find all the points that lie within a given rectangle (or higher-dimensional region analogous to a rectangle). This operation is also called an orthogonal range search. (Undone) ===Determining where to evaluate a surface=== In local regression, it is common to evaluate the fitted surface directly only at the vertices of a ''k''d-tree and to interpolate elsewhere. This use, which is pictured in the image above, is to ensure that only as many direct evaluations are performed as are necessary. Since the ''k''d-tree "adapts" itself to the space of predictor variables, this method can provide an excellent approximation to the true local regression surface. If the approximation is poor, it can be improved by further subdivision of the tree's cells. ==Complexity== * Building a static ''k''d-tree from ''n'' points takes Big O notation(''n'' log ''n'') time. * Inserting a new point into a balanced ''k''d-tree takes O(log ''n'') time. * Removing a point from a balanced ''k''d-tree takes O(log ''n'') time. ==External links== * [http://www.rolemaker.dk/nonRoleMaker/uni/algogem/kdtree.htm Java applet demonstrating 2-dimensional ''k''d-trees] Computer science Computer graphics Trees (structure)
See other meanings of words starting from letter:
K
KA | KB | KC | KD | KE | KF | KG | KH | KI | KJ | KL | KM | KN | KO | KP | KR | KS | KT | KU | KW | KX | KY | KZ |Words begining with Kd-tree:
Kd-tree
These materials are based on Wikipedia and licensed under the GNU FDL
YouTube.com videos better site than Turbo Tax 2007
