View source for Decomposition

A decomposition is a representation of a given set as the union of a system of pairwise disjoint sets.

In discrete geometry one frequently considers the decomposition of some space into closed domains which cover the entire space and whose pairwise intersections have no interior points (they may have common boundary points). For example, if one fixes any point lattice in the Euclidean space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d030/d030480/d0304801.png" /> and assigns to each point of the lattice those points of the space that are less distant from this point than from any other point of the lattice, then the so-called Dirichlet–Voronoi decomposition is obtained. A decomposition of a space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d030/d030480/d0304802.png" /> is called regular if for any domains <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d030/d030480/d0304803.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d030/d030480/d0304804.png" /> in it there is a motion <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d030/d030480/d0304805.png" /> for which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d030/d030480/d0304806.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d030/d030480/d0304807.png" />. See also [[Voronoi lattice types|Voronoi lattice types]].

In combinatorial geometry there are several problems and results relating to particular decompositions of certain sets. An example of such a problem is the [[Borsuk problem|Borsuk problem]]: Is it possible to divide any set of diameter <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d030/d030480/d0304808.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d030/d030480/d0304809.png" /> into <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d030/d030480/d03048010.png" /> parts, each of them having diameter less than <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d030/d030480/d03048011.png" />? In <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d030/d030480/d03048012.png" /> there are bounded sets for which a decomposition into a smaller number of such parts is impossible. Any decomposition determines a certain covering (cf. [[Covering (of a set)|Covering (of a set)]]) and from any covering one can obtain a decomposition. Decompositions are closely connected with the [[Illumination problem|illumination problem]] and the [[Hadwiger hypothesis|Hadwiger hypothesis]].

====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  V.G. Boltyanskii,   P.S. Soltan,   "The combinatorial geometry of various classes of convex sets" , Kishinev  (1978)  (In Russian)</TD></TR><TR><TD valign="top">[2a]</TD> <TD valign="top">  B. Grünbaum,   "Borsuk's problem and related questions"  V.L. Klee (ed.) , ''Convexity'' , ''Proc. Symp. Pure Math.'' , '''7''' , Amer. Math. Soc.  (1963)  pp. 271–284</TD></TR><TR><TD valign="top">[2b]</TD> <TD valign="top">  B. Grünbaum,   "Measures of symmetry for convex sets"  V.L. Klee (ed.) , ''Convexity'' , ''Proc. Symp. Pure Math.'' , '''7''' , Amer. Math. Soc.  (1963)  pp. 233–270</TD></TR></table>



====Comments====


====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  V.G. Boltyanskii,   I.Ts. Gokhberg,   "Sätze und Probleme der Kombinatorische Geometrie" , Deutsch. Verlag Wissenschaft.  (1972)  (Translated from Russian)</TD></TR></table>

A decomposition of a space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d030/d030480/d03048013.png" /> is a system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d030/d030480/d03048014.png" /> of disjoint subsets with union <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d030/d030480/d03048015.png" />. The set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d030/d030480/d03048016.png" /> becomes a topological space if one defines its open sets to be all the sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d030/d030480/d03048017.png" /> whose pre-images under the natural mapping <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d030/d030480/d03048018.png" /> (assigning to each point <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d030/d030480/d03048019.png" /> the unique set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d030/d030480/d03048020.png" /> containing it) are open sets in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d030/d030480/d03048021.png" />.

====Comments====
A decomposition <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d030/d030480/d03048022.png" /> defines an equivalence relation in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d030/d030480/d03048023.png" /> (and inversely of course). The topology on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d030/d030480/d03048024.png" /> makes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d030/d030480/d03048025.png" /> the quotient space of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d030/d030480/d03048026.png" /> for this equivalence relation.

A decomposition is a locally finite covering of a space whose elements are canonical closed sets with disjoint open kernels.

''M.I. Voitsekhovskii''

====Comments====
Instead of the word  "decomposition" ,  "partition"  is often used (in all three cases). However,  "partition"  has also other (natural) meanings, e.g. cf. [[Partition]]. See also, e.g., [[Measurable decomposition]].