Densitate de împachetare

În matematică densitatea de împachetare sau fracția de împachetare a unui împachetări într-un anumit spațiu este fracțiunea spațiului umplut de figurile care formează împachetarea. În cuvinte simple, acesta este raportul dintre volumul corpurilor dintr-un spațiu și volumul spațiului însuși. În problemele de împachetare, obiectivul este de obicei obținerea unei împachetări cu cea mai mare densitate posibilă.

În spații compacte

Dacă $K 1, ... , K n$ sunt subseturi măsurabile ale măsurii unui spațiu compact $X$ , iar interioarele lor perechi nu se intersectează, atunci colecția $[K i]$ este o împachetare în $X$ cu densitatea de împachetare

\eta ={\frac {\sum _{i=1}^{n}\mu (K_{i})}{\mu (X)}}

.

În spațiul euclidian

Dacă spațiul care este împachetat este infinit ca măsură, cum ar fi spațiul euclidian, se obișnuiește să se definească densitatea ca limită a densității realizate de bile cu raze din ce în ce mai mari. Dacă $B t$ este bila cu raza $t$ centrată în origine, atunci densitatea unei împachetări $\mathbb {N}$ este

\eta =\lim _{t\to \infty }{\frac {\sum _{i=1}^{\infty }\mu (K_{i}\cap B_{t})}{\mu (B_{t})}}

.

Deoarece această limită nu există întotdeauna, este de asemenea util să se definească densitățile superioară și inferioară ca limită superioară, respectiv limită inferioară ale celor de mai sus. Dacă densitatea există, densitățile superioară și inferioară sunt egale. Cu condiția ca orice bilă din spațiul euclidian să intersecteze doar un număr finit de elemente ale împachetării și ca diametrele elementelor să fie mărginite în sus, densitatea (superioară, inferioară) nu depinde de alegerea originii, iar $μ (K i \cap B t)$ poate fi înlocuit cu $μ (K i)$ la orice element care intersectează $B t$ .^[1] Bila poate fi înlocuită cu dilatări ale unui alt corp convex, dar, în general, densitățile rezultate nu sunt egale.

Densitatea de împachetare optimă

Uneori există interes în împachetări limitate la elementele unei anumite colecții (provizii). De exemplu, colecția de provizii poate fi mulțimea tuturor bilelor cu o rază dată. Densitatea optimă de împachetare sau constanta împachetării asociate unei colecții este cea mai mare densitate obținută prin împachetare a subcolecțiilor colecției. Dacă colecția constă din corpuri convexe cu diametru limitat, există o împachetare a cărei densitate de împachetare este egală cu constanta împachetării, iar această constantă a împachetării nu variază dacă bilele din definiția densității sunt înlocuite cu dilatații ale unui alt corp convex.^[1]

O anumită colecție prezintă interes pentru toate transformările rigide (deplasări, rotații etc.) ale unui corp convex dat, $K$ . În acest caz constanta împachetării este constanta împachetării lui $K$ . Conjectura Kepler^⁠(d) se referă la constanta împachetării bilelor tridimensionale. Conjectura de împachetare a lui Ulam afirmă că bilele tridimensionale au cea mai mică constantă de împachetare dintre toate corpurile convexe. De asemenea, toate translațiile unui corp dat formează o colecție, care prezintă de obicei interes și definește constanta de împachetare a translațiilor acelui corp.

Note

^ ^a ^b en Groemer, H. (1986), „Some basic properties of packing and covering constants”, Discrete and Computational Geometry, 1 (2): 183–193, doi:10.1007/BF02187693

Legături externe

Portal Matematică

en Eric W. Weisstein, Packing Density la MathWorld.

[groemer1986-1] Groemer, H. (1986), „Some basic properties of packing and covering constants”, Discrete and Computational Geometry, 1 (2): 183–193, doi:10.1007/BF02187693 

[1]