A dimension is an independent coordinate axis or degree of freedom needed to specify a point. A one-dimensional value uses one coordinate; a point in ℝ² uses two. More generally, a k-dimensional point can be represented as a k-tuple of values. section 8.4.2 section 10.3
Dimension affects how data can be organized. Binary search divides a one-dimensional range into halves, but a plane has no single obvious left-right split. Partitioning only by x-coordinate ignores y-coordinate information and can separate nearby points while grouping less-similar ones. section 8.4.2
In multidimensional indexes, dimensionality determines both representation and operations:
- A k-d tree cycles through coordinate dimensions as tree levels determine splitting coordinates. section 9.3.4
- Deleting from a k-d tree must preserve coordinate-based splitting invariants; replacing a node as in a binary search tree can violate them. section 9.3.4
- An SS-tree stores k-dimensional points at leaves and records dimensionality k alongside node capacity parameters. section 10.3
A misleading two-dimensional split
Suppose a point R is used to split a Cartesian plane with a vertical line. Points are assigned by x-coordinate, even though pairs such as U and S may be closer than pairs placed in the same partition. The y-coordinate is essential to represent their spatial relationship. section 8.4.2
Figure 8.8 Points in a Cartesian plane. Lines through the origin and each point are shown. A few possible partitionings into left and right of P are shown. (A) Splitting the plane with a vertical line passing through P. (B) Drawing a line passing through P and the origin will define two semi-spaces on the two sides of the line. (C) Using the same line as B but partitioning points whose projection on that line is left or right of P.
Compare vertical splitting, line-based half-spaces, and projection-based partitioning in a two-dimensional plane. section 8.4.2
