|
|
| (13 intermediate revisions by 2 users not shown) |
| Line 1: |
Line 1: |
| − | ''of a finite (or infinite) family of sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071050/p0710501.png" /> in a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071050/p0710502.png" />''
| + | {{MSC|52C20|52C22}} |
| | + | {{TEX|done}} \( \def \Z { {\cal Z}} \) |
| | | | |
| − | Fulfillment of the conditions
| + | A '''packing''' of a (finite or infinite) family of sets $M_i$ in a set $A$ is, in its strict sense, |
| | + | any pairwise disjoint family of subsets $M_i\subset A$. |
| | | | |
| − | <table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071050/p0710503.png" /></td> </tr></table>
| + | However, in geometry, for packings in Euclidean spaces, |
| | + | on an $n$-dimensional sphere, in a closed domanin, or in some other manifold, the sets $M_i$ are often closed domains, |
| | + | and then this condition is relaxed to requiring only that the interiors of the sets are pairwise disjoint. |
| | | | |
| − | In the [[Geometry of numbers|geometry of numbers]] usually <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071050/p0710504.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071050/p0710505.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071050/p0710506.png" /> is a given set and the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071050/p0710507.png" /> range over a certain set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071050/p0710508.png" /> of vectors in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071050/p0710509.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071050/p07105010.png" />); in this case one speaks of the packing <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071050/p07105011.png" /> of the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071050/p07105012.png" /> by the system of vectors <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071050/p07105013.png" />. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071050/p07105014.png" /> is a point lattice in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071050/p07105015.png" />, one speaks of a lattice packing <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071050/p07105016.png" />.
| + | ==== Lattice packings ==== |
| − | | |
| − | One also considers packing of sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071050/p07105017.png" /> not only in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071050/p07105018.png" /> but also in other manifolds, on an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071050/p07105019.png" />-dimensional sphere, in a given domain, etc. (cf. [[#References|[1]]], [[#References|[2]]]). Sometimes a packing is defined as a system of (for example, closed domains) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071050/p07105020.png" /> which do not meet in interior points (cf. [[#References|[1]]]).
| |
| − | | |
| − | ====References====
| |
| − | <table><TR><TD valign="top">[1]</TD> <TD valign="top"> E.P. Baranovskii, "Packings, coverings, partitions, and certain other distributions in spaces of constant curvature" ''Progress in Math.'' , '''9''' (1971) pp. 209–253 ''Itogi Nauk. Algebra. Topol. Geom. 1967'' (1969) pp. 181–225</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top"> L. Fejes Toth, "Lagerungen in der Ebene, auf der Kugel und im Raum" , Springer (1972)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top"> C.A. Rogers, "Packing and covering" , Cambridge Univ. Press (1964)</TD></TR></table>
| |
| | | | |
| | + | As a special case, in vector spaces $V$, such as $\R^d$, |
| | + | packings of translates $ \{ M+v \mid v \in \Z \} $, of a set $ M \subset V $ |
| | + | (also called the packing $(M,\Z)$ of $M$ ''by'' $\Z$) are considered. |
| | + | If the set $ \Z \subset V $ of translation vectors is a point lattice, |
| | + | then the packing is called a '''[[lattice packing]]'''. |
| | + | In particular, such packings are investigated in the geometry of numbers and in discrete geometry. |
| | | | |
| | + | ==== Sphere packings ==== |
| | | | |
| − | ====Comments====
| + | Packings of congruent spheres are considered both in the geometry of numbers |
| − | Sphere packing has various applications in error-correcting codes (cf. [[Error-correcting code|Error-correcting code]]), the channel coding problem, Steiner systems (cf. [[Steiner system|Steiner system]]), <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071050/p07105021.png" />-designs, and in the theory of finite groups. The most important special case is the sphere packing in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071050/p07105022.png" /> via the [[Leech lattice|Leech lattice]]. Finite and infinite sphere packing in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071050/p07105023.png" /> has applications in classical and modern crystallography (cf. [[Crystallography, mathematical|Crystallography, mathematical]]).
| + | and in discrete geometry, and have applications in coding theory. |
| | + | A central problem is finding the densest packing, |
| | + | and the densest lattice packing, of congruent spheres in $\R^d$. |
| | + | For $d=3$, the problem (known as Kepler conjecture or [[Kepler problem]]) |
| | + | to decide whether there is a better packing than the densest lattice packing |
| | + | was a famous open problem that was recently solved by Hales (1998). |
| | + | With the help of massive computer calculations he showed |
| | + | that the densest lattice packing of spheres is optimal. |
| | + | This result is generally considered as correct |
| | + | but because of its size it has not yet been verified independently. |
| | + | However, Hales and his team are working on a computer-verifyable version of the proof. |
| | | | |
| − | A packing in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071050/p07105024.png" /> which is also a covering in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071050/p07105025.png" /> (cf. [[Covering and packing|Covering and packing]]; [[Covering (of a set)|Covering (of a set)]]) is called a tiling or tesselation. In other words: A tiling is a countable family of closed sets which cover <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071050/p07105026.png" /> without gaps or overlaps. The sets are called tiles. If all sets are congruent, they are the copies of a prototile.
| + | ==== Tilings ==== |
| | | | |
| − | In the [[Geometry of numbers|geometry of numbers]], lattice tilings are of interest; there are tilings of the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071050/p07105027.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071050/p07105028.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071050/p07105029.png" /> is a [[Lattice of points|lattice of points]]. For an exhaustive account of planar tilings see [[#References|[a3]]]. Higher-dimensional results and, in particular, relations to crystallography are treated in [[#References|[a2]]], [[#References|[a1]]]. Classical types of tilings are Dirichlet–Voronoi tilings and Delone triangulations or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071050/p07105031.png" />-partitions, see [[#References|[a1]]] and [[Voronoi lattice types|Voronoi lattice types]].
| + | A '''[[tiling]]''' is a packing without gaps, |
| | + | i.e., such that the $M_i$ are also a covering of $A$. |
| | | | |
| | ====References==== | | ====References==== |
| − | <table><TR><TD valign="top">[a1]</TD> <TD valign="top"> P. Erdös, P.M. Gruber, J. Hammer, "Lattice points" , Longman (1989)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top"> P.M. Gruber, C.G. Lekkerkerker, "Geometry of numbers" , North-Holland (1987) pp. Sect. (iv) (Updated reprint)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top"> B. Grünbaum, G.C. Shephard, "Tilings and patterns" , Freeman (1986)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top"> J.H. Conway, N.J.A. Sloane, "Sphere packing, lattices and groups" , Springer (1988)</TD></TR></table>
| + | {| |
| | + | |- |
| | + | |valign="top"|{{Ref|Ba}}|| valign="top"| E.P. Baranovskiĭ, "Packings, coverings, partitionings and certain other arrangements in spaces with constant curvature" (1969) Algebra. Topology. Geometry. (1967) (Russian) pp. 189–225 Akad. Nauk SSSR Vsesojuz. Inst. Naučn. Tehn. Informacii, Moscow {{MR|0257885}} |
| | + | |- |
| | + | |valign="top"|{{Ref|CoSl}}||valign="top"| J.H. Conway, N.J.A. Sloane, "Sphere packing, lattices and groups", Springer (1988) {{MR|0920369}} |
| | + | |- |
| | + | | valign="top"|{{Ref|FeTo}}||valign="top"| L. Fejes Tóth, "Lagerungen in der Ebene, auf der Kugel und im Raum", Springer (1972) {{MR|0353117}} {{ZBL|0229.52009}} |
| | + | |- |
| | + | | valign="top"|{{Ref|Ro}}||valign="top"| C.A. Rogers, "Packing and covering", Cambridge Univ. Press (1964) {{MR|0172183}} {{ZBL|0176.51401}} |
| | + | |- |
| | + | |} |
2020 Mathematics Subject Classification: Primary: 52C20 Secondary: 52C22 [MSN][ZBL] \( \def \Z { {\cal Z}} \)
A packing of a (finite or infinite) family of sets $M_i$ in a set $A$ is, in its strict sense,
any pairwise disjoint family of subsets $M_i\subset A$.
However, in geometry, for packings in Euclidean spaces,
on an $n$-dimensional sphere, in a closed domanin, or in some other manifold, the sets $M_i$ are often closed domains,
and then this condition is relaxed to requiring only that the interiors of the sets are pairwise disjoint.
Lattice packings
As a special case, in vector spaces $V$, such as $\R^d$,
packings of translates $ \{ M+v \mid v \in \Z \} $, of a set $ M \subset V $
(also called the packing $(M,\Z)$ of $M$ by $\Z$) are considered.
If the set $ \Z \subset V $ of translation vectors is a point lattice,
then the packing is called a lattice packing.
In particular, such packings are investigated in the geometry of numbers and in discrete geometry.
Sphere packings
Packings of congruent spheres are considered both in the geometry of numbers
and in discrete geometry, and have applications in coding theory.
A central problem is finding the densest packing,
and the densest lattice packing, of congruent spheres in $\R^d$.
For $d=3$, the problem (known as Kepler conjecture or Kepler problem)
to decide whether there is a better packing than the densest lattice packing
was a famous open problem that was recently solved by Hales (1998).
With the help of massive computer calculations he showed
that the densest lattice packing of spheres is optimal.
This result is generally considered as correct
but because of its size it has not yet been verified independently.
However, Hales and his team are working on a computer-verifyable version of the proof.
Tilings
A tiling is a packing without gaps,
i.e., such that the $M_i$ are also a covering of $A$.
References
| [Ba] |
E.P. Baranovskiĭ, "Packings, coverings, partitionings and certain other arrangements in spaces with constant curvature" (1969) Algebra. Topology. Geometry. (1967) (Russian) pp. 189–225 Akad. Nauk SSSR Vsesojuz. Inst. Naučn. Tehn. Informacii, Moscow MR0257885
|
| [CoSl] |
J.H. Conway, N.J.A. Sloane, "Sphere packing, lattices and groups", Springer (1988) MR0920369
|
| [FeTo] |
L. Fejes Tóth, "Lagerungen in der Ebene, auf der Kugel und im Raum", Springer (1972) MR0353117 Zbl 0229.52009
|
| [Ro] |
C.A. Rogers, "Packing and covering", Cambridge Univ. Press (1964) MR0172183 Zbl 0176.51401
|