A point represents a position in a multidimensional space as an ordered collection of coordinate values. In a k-dimensional space, it is a k-element tuple whose coordinates can be compared. section 9.2.1
Points support multidimensional indexing and geometric queries:
- A k-d tree stores points as elements of a binary search tree, comparing a different coordinate at each tree level. section 9.2.1
- Nearest-neighbor structures can retrieve the closest point, the N closest points, or points inside a specified region. section 8.3
- Coordinates need not represent physical axes; they can encode attributes such as price and rating when a suitable Euclidean distance is defined. section 8.3
A point with application-specific coordinates
The tuple (100$, 4.5 rating) can represent an item whose first coordinate is price and whose second coordinate is rating. A nearest-neighbor query can compare it with stored points and return the closest item. section 8.3
Figure 9.3 Constructing a BST from the pivots of a 1-D dataset. (Left) We add the first pivot, which is going to be the root of the tree. The pivot creates an implicit divide along the x axis, partitioning the remaining points into left and right subsets. The region covered by a node is the union of the partitions its pivot creates, so the root covers the whole subset. (Center) Each of the two sub-regions implied by the root is further partitioned by selecting a point in each region as a pivot. As shown by the highlighting above the horizontal axis, each of these nodes at level 1 now covers half of the space (while the root still covers the whole space). (Right) Level 2 nodes are added, further partitioning the space. Notice how some regions are still only covered by nodes at level 1 because these intermediate nodes only have one child.
Visualizes how points become pivots that partition a one-dimensional dataset into progressively smaller regions in a binary search tree. section 9.2.1
