Abstract Space Partitioning / Space Partitioning ADT

Space partitioning involves the recursive division of a Cartesian coordinate space into disjoint subsets. Usually this is a regular partition into two, four or eight subspaces, however; even this regularity is not required.

  • Binary space-partitioning trees (BSP trees),
  • Quadtrees,
  • Octtrees,
  • k-d trees,
  • R-trees

Partitioning a Vector Space into Two Regions

An elegant property of a vector space is that all planes are defined by an equation of the form

tex:$$ a_1{\bf x}_1 + a_2{\bf x}_2 + \mdots \a_n{\bf x}_n = c $$

and this may be used to partition the space into three regions:

  • Those on one side of the plane,
  • Those on the plane, and
  • Those on the other side of the plane.

If tex:$$ {\bf p} $$ is any vector on the plane and tex:$$ {\bf a} = (a_1, a_2, \ldots, a_n)^T $$ then a vector tex:$$ {\bf v} $$ falls into one of these categories based on whether tex:$$ ({\bf v} - {\bf v})\mdot{\bf a} $$ is less than, equal to, or greater than zero.