A projection maps points onto a selected axis or lower-dimensional subspace by retaining their coordinates in that direction. In two-dimensional algorithms, projecting onto an axis reduces geometric relationships to one-dimensional coordinate comparisons. section 15.4.1 section 10.3.4
Projection supports several practical algorithmic operations:
- Screen segment intersections by comparing projections on the x and y axes. Non-overlapping projections on either axis prove that the segments cannot intersect; overlapping projections require a further test. section 15.4.1
- Split points in a similarity-search tree by projecting them onto the direction of maximum variance, sorting their coordinates, and choosing a variance-minimizing split index. section 10.3.4
- Visualize higher-dimensional optimization by projecting a three-dimensional function plot into two dimensions or fixing all but two variables. section 16.2
Axis projection during a tree split
Suppose a node contains eight points and its direction of maximum variance is the y axis. Projecting onto that axis means retaining each point’s y coordinate, sorting those values, and testing valid split positions. The chosen position minimizes the sum of the two partitions’ variances while respecting the node’s minimum-entry constraint. section 10.3.4
Figure 15.16 Examples of non-intersecting segments: the bounding-box check can only rule out an intersection, but cannot confirm it.
Compare projected segment intervals with their axis-aligned bounding boxes to see why projection can rule out intersections but cannot confirm them. section 15.4.1
