A hyperplane is a flat boundary with one fewer dimension than its surrounding space. It divides that space into two half-spaces, placing points on opposite sides. section 8.3 section 12.2.1
The same geometric idea supports two practical tasks:
- Partitioning a k-dimensional search space: each non-leaf k-d tree node uses a splitting hyperplane, storing points from each half-space in a different subtree. section 8.3
- Testing linear separability: two sets are linearly separable when a hyperplane places every point from one set on one side and every point from the other set on the opposite side. section 12.2.1
Linear clusters
Two nearby linear clusters may be separated by a hyperplane, while concentric rings and spirals cannot be separated this way; this is one reason k-means fails on non-convex clusters. section 12.2.1
Figure 12.6 Three examples where the clustering result produced by k-means can never be optimal. (Left) Two concentric rings (two centroids). (Right) A spiral (three centroids: the optimal solution here would be to have a single cluster). (Bottom) Two linear clusters close to each other.
Compare the linear-cluster example with concentric rings and a spiral to see when hyperplane-based separation is possible. section 12.2.1
