improve the execution time of ray tracing for three-dimensional computer graphics. These algorithms presort n triangles prior to building the , then build the tree in time in the best case. An algorithm that builds a balanced to sort points has a worst-case complexity of . This algorithm presorts n points in each of k dimensions using an sort such as Heapsort or Mergesort prior to building the tree. It then maintains the order of these k presorts during tree construction and thereby avoids finding the median at each level of subdivision. Adding elements One adds a new point to a k-d tree in the same way as one adds an element to any other search 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 the node under which the child should be located, 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 node. Adding points in this manner can cause the tree to become unbalanced, leading to decreased tree performance. The rate of tree performance degradation is dependent upon the spatial distribution of tree points being added, and the number of points added in relation to the tree size. If a tree becomes too unbalanced, it may need to be re-balanced to restore the performance of queries that rely on the tree balancing, such as nearest neighbour searching. Removing elements To remove a point from an existing k-d tree, without breaking the invariant, the easiest way is to form the set of all nodes and leaves from the children of the target node, and recreate that part of the tree. Another approach is to find a replacement for the point removed. First, find the node that contains the point to be removed. For the base case where R is a leaf node, no replacement is required. For the general case, find a replacement point, say , from the subtree rooted at . Replace the point stored at with . Then, recursively remove . For finding a replacement point, if discriminates on (say) and has a right child, find the point with the minimum value from the subtree