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.