Space partitioning
Division of a space into ≥2 disjoint subsets
In geometry , space partitioning is the process of dividing a space (usually a Euclidean space ) into two or more disjoint subsets (see also partition of a set ). In other words, space partitioning divides a space into nonoverlapping regions. Any point in the space can then be identified to lie in exactly one of the regions.
Overview
Spacepartitioning systems are often hierarchical , meaning that a space (or a region of space) is divided into several regions, and then the same spacepartitioning system is recursively applied to each of the regions thus created. The regions can be organized into a tree , called a spacepartitioning tree .
Most spacepartitioning systems use planes (or, in higher dimensions, hyperplanes ) to divide space: points on one side of the plane form one region, and points on the other side form another. Points exactly on the plane are usually arbitrarily assigned to one or the other side. Recursively partitioning space using planes in this way produces a BSP tree , one of the most common forms of space partitioning.
Uses
In computer graphics
Space partitioning is particularly important in computer graphics , especially heavily used in ray tracing , where it is frequently used to organize the objects in a virtual scene. A typical scene may contain millions of polygons. Performing a ray/polygon intersection test with each would be a very computationally expensive task.
Storing objects in a spacepartitioning data structure ( k d tree or BSP tree for example) makes it easy and fast to perform certain kinds of geometry queries—for example in determining whether a ray intersects an object, space partitioning can reduce the number of intersection test to just a few per primary ray, yielding a logarithmic time complexity with respect to the number of polygons. ^{ [1] } ^{ [2] } ^{ [3] }
Space partitioning is also often used in scanline algorithms to eliminate the polygons out of the camera's viewing frustum , limiting the number of polygons processed by the pipeline. There is also a usage in collision detection : determining whether two objects are close to each other can be much faster using space partitioning.
In integrated circuit design
In integrated circuit design , an important step is design rule check . This step ensures that the completed design is manufacturable. The check involves rules that specify widths and spacings and other geometry patterns. A modern design can have billions of polygons that represent wires and transistors. Efficient checking relies heavily on geometry query. For example, a rule may specify that any polygon must be at least n nanometers from any other polygon. This is converted into a geometry query by enlarging a polygon by n/2 at all sides and query to find all intersecting polygons.
In probability and statistical learning theory
The number of components in a space partition plays a central role in some results in probability theory. See Growth function for more details.
In Geography and GIS
There are many studies and applications where Geographical Spatial Reality is partitioned by hydrological criteria , administrative criteria , mathematical criteria or many others.
In the context of Cartography and GIS  Geographic Information System , is common to identify cells of the partition by standard codes . For example the for HUC code identifying hydrographical basins and subbasins, ISO 31662 codes identifying countries and its subdivisions, or arbitrary DGGs  discrete global grids identifying quadrants or locations.
Data structures
Common spacepartitioning systems include:
Number of components
Suppose the ndimensional Euclidean space is partitioned by $r\; \{\backslash displaystyle\; r\}$ hyperplanes that are $(\; n\; \; 1\; )\; \{\backslash displaystyle\; (n1)\}$ dimensional. What is the number of components in the partition? The largest number of components is attained when the hyperplanes are in general position , i.e, no two are parallel and no three have the same intersection. Denote this maximum number of components by $C\; o\; m\; p\; (\; n\; ,\; r\; )\; \{\backslash displaystyle\; Comp(n,r)\}$ . Then, the following recurrence relation holds: ^{ [4] } ^{ [5] }

 $C\; o\; m\; p\; (\; n\; ,\; r\; )\; =\; C\; o\; m\; p\; (\; n\; ,\; r\; \; 1\; )\; +\; C\; o\; m\; p\; (\; n\; \; 1\; ,\; r\; \; 1\; )\; \{\backslash displaystyle\; Comp(n,r)=Comp(n,r1)+Comp(n1,r1)\}$
 $C\; o\; m\; p\; (\; 0\; ,\; r\; )\; =\; 1\; \{\backslash displaystyle\; Comp(0,r)=1\}$  when there are no dimensions, there is a single point.
 $C\; o\; m\; p\; (\; n\; ,\; 0\; )\; =\; 1\; \{\backslash displaystyle\; Comp(n,0)=1\}$  when there are no hyperplanes, all the space is a single component.
And its solution is:

 $C\; o\; m\; p\; (\; n\; ,\; r\; )\; =\; \sum \; k\; =\; 0\; n\; (\; r\; k\; )\; \{\backslash displaystyle\; Comp(n,r)=\backslash sum\; \_\{k=0\}^\{n\}\{r\; \backslash choose\; k\}\}$ if $r\; \ge \; n\; \{\backslash displaystyle\; r\backslash geq\; n\}$

$C\; o\; m\; p\; (\; n\; ,\; r\; )\; =\; 2\; r\; \{\backslash displaystyle\; Comp(n,r)=2^\{r\}\}$
if
$r\; \le \; n\; \{\backslash displaystyle\; r\backslash leq\; n\}$

 (consider e.g. $r\; \{\backslash displaystyle\; r\}$ perpendicular hyperplanes; each additional hyperplane divides each existing component to 2).

which is upperbounded as:

 $C\; o\; m\; p\; (\; n\; ,\; r\; )\; \le \; r\; n\; +\; 1\; \{\backslash displaystyle\; Comp(n,r)\backslash leq\; r^\{n\}+1\}$
See also
References
 ↑ Tomas Nikodym (2010). "Ray Tracing Algorithm For Interactive Applications" (PDF) . Czech Technical University, FEE .
 ↑ Ingo Wald, William R. Mark; et al. (2007). "State of the Art in Ray Tracing Animated Scenes". Eurographics . CiteSeerX 10.1.1.108.8495 .
 ↑ Ray Tracing  Auxiliary Data Structures
 ↑ Vapnik, V. N.; Chervonenkis, A. Ya. (1971). "On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities". Theory of Probability & Its Applications . 16 (2): 266. doi : 10.1137/1116025 . This is an English translation, by B. Seckler, of the Russian paper: "On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities". Dokl. Akad. Nauk . 181 (4): 781. 1968. The translation was reproduced as: Vapnik, V. N.; Chervonenkis, A. Ya. (2015). "On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities". Measures of Complexity . p. 11. doi : 10.1007/9783319218526_3 . ISBN 9783319218519 .
 ↑ See also detailed discussions and explanations on the case n=2 and the general case . See also Winder, R. O. (1966). "Partitions of NSpace by Hyperplanes". SIAM Journal on Applied Mathematics . 14 (4): 811–818. doi : 10.1137/0114068 . .