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.
An elegant property of a vector space is that all planes are defined by an equation of the form
and this may be used to partition the space into three regions:
If is any vector on the plane and then a vector falls into one of these categories based on whether is less than, equal to, or greater than zero.