Define a split tree and its applications in computational geometry.

A split tree is a data structure used in computational geometry to efficiently answer range queries.

A split tree, also known as a range tree, is a type of binary tree that is used to store a list of points. Each node in the tree represents an interval or range of values, and the tree is structured such that for any given node, all the nodes in its left subtree represent intervals that are entirely less than its own interval, and all the nodes in its right subtree represent intervals that are entirely greater. This makes it possible to quickly locate a specific interval or range of values, which is particularly useful in computational geometry for tasks such as finding all the points that lie within a certain range.

The split tree is constructed by first sorting the list of points, and then recursively dividing the list into two halves until each interval contains only one point. This results in a balanced binary tree, where the height of the tree is proportional to the logarithm of the number of points. This means that the time complexity of searching for a specific interval in the tree is logarithmic in the number of points, which is significantly faster than linear search.

In addition to range queries, split trees can also be used to answer nearest neighbour queries, where the task is to find the point that is closest to a given query point. This is done by traversing the tree to find the node that represents the interval containing the query point, and then comparing the distance to the query point with the distances to the points in the neighbouring intervals.

Split trees are also used in the construction of other data structures in computational geometry, such as segment trees and interval trees, which are used for tasks such as detecting intersections between line segments and finding all intervals that overlap with a given interval. These applications make split trees a fundamental tool in computational geometry, with uses in areas such as computer graphics, geographic information systems, and machine learning.