Problemas de embalaje

Estos problemas son matemáticamente distintos de las ideas del teorema de empaquetamiento de círculos . El problema relacionado del empaquetamiento de círculos trata de empaquetar círculos , posiblemente de diferentes tamaños, sobre una superficie, por ejemplo, un plano o una esfera .

Las contrapartes de un círculo en otras dimensiones nunca pueden empaquetarse con total eficiencia en dimensiones mayores que una (en un universo unidimensional, el análogo del círculo son solo dos puntos). Es decir, siempre habrá espacio sin usar si solo se empaquetan círculos. La forma más eficiente de empaquetar círculos, el empaquetamiento hexagonal , produce aproximadamente un 91 % de eficiencia. ^{[ 8 ]}

En tres dimensiones, las estructuras compactas ofrecen el mejor empaquetamiento reticular de esferas y se consideran el óptimo de todos los empaquetamientos. Con empaquetamientos de esferas "simples" en tres dimensiones (donde "simple" se define cuidadosamente) existen nueve empaquetamientos definibles posibles. ^{[ 9 ]} También se ha demostrado que la red E8 de 8 dimensiones y la red Leech de 24 dimensiones son óptimas en sus respectivos espacios de dimensiones reales.

Los cubos se pueden organizar fácilmente para llenar completamente el espacio tridimensional, siendo el panal cúbico la forma de empaquetamiento más natural . Ningún otro sólido platónico puede recubrir el espacio por sí solo, pero se conocen algunos resultados preliminares. Los tetraedros pueden alcanzar un empaquetamiento de al menos el 85 %. Uno de los mejores empaquetamientos de dodecaedros regulares se basa en la red cúbica centrada en las caras (FCC) mencionada anteriormente.

Los tetraedros y los octaedros juntos pueden llenar todo el espacio en una disposición conocida como panal tetraédrico-octaédrico .

Las simulaciones que combinan métodos de mejora local con empaquetamientos aleatorios sugieren que los empaquetamientos reticulares para icosaedros, dodecaedros y octaedros son óptimos en la clase más amplia de todos los empaquetamientos. ^{[ 3 ]}

Determina el número mínimo de contenedores cúbicos necesarios para empaquetar un conjunto dado de cuboides. Los cuboides rectangulares que se van a empaquetar pueden girar 90 grados sobre cada eje.

El problema de encontrar la bola más pequeña tal que k bolas unitarias abiertas disjuntas puedan empaquetarse dentro de ella tiene una respuesta simple y completa en el espacio euclidiano n- dimensional si${\displaystyle k\leq n+1}$y en un espacio de Hilbert de dimensión infinita sin restricciones. Vale la pena describirlo en detalle aquí, para dar una idea del problema general. En este caso, se dispone de una configuración de k bolas unitarias tangentes por pares . Se colocan los centros en los vértices.${\displaystyle a_{1},\dots ,a_{k}}$de un regular${\displaystyle (k-1)}$simplex dimensional con arista 2; esto se realiza fácilmente partiendo de una base ortonormal . Un pequeño cálculo muestra que la distancia de cada vértice al baricentro es${\textstyle {\sqrt {2{\big (}1-{\frac {1}{k}}{\big )}}}}$Además, cualquier otro punto del espacio necesariamente tiene una mayor distancia de al menos uno de los k vértices. En términos de inclusiones de bolas, las k bolas unitarias abiertas centradas en${\displaystyle a_{1},\dots ,a_{k}}$están incluidos en una bola de radio${\textstyle r_{k}:=1+{\sqrt {2{\big (}1-{\frac {1}{k}}{\big )}}}}$, que es mínimo para esta configuración.

Para demostrar que esta configuración es óptima, dejemos${\displaystyle x_{1},\dots ,x_{k}}$sean los centros de k bolas unitarias abiertas disjuntas contenidas en una bola de radio r centrada en un punto${\displaystyle x_{0}}$. Consideremos la aplicación del conjunto finito${\displaystyle \{x_{1},\dots ,x_{k}\}}$en${\displaystyle \{a_{1},\dots ,a_{k}\}}$tomando${\displaystyle x_{j}}$en el correspondiente${\displaystyle a_{j}}$para cada${\displaystyle 1\leq j\leq k}$. Dado que para todos${\displaystyle 1\leq i<j\leq k}$,${\displaystyle \|a_{i}-a_{j}\|=2\leq \|x_{i}-x_{j}\|}$Este mapa es 1- Lipschitz y, por el teorema de Kirszbraun, se extiende a un mapa 1-Lipschitz definido globalmente; en particular, existe un punto${\displaystyle a_{0}}$de tal manera que para todos${\displaystyle 1\leq j\leq k}$uno tiene${\displaystyle \|a_{0}-a_{j}\|\leq \|x_{0}-x_{j}\|}$, para que también${\displaystyle r_{k}\leq 1+\|a_{0}-a_{j}\|\leq 1+\|x_{0}-x_{j}\|\leq r}$Esto demuestra que hay k bolas abiertas unitarias disjuntas en una bola de radio r si y solo si${\displaystyle r\geq r_{k}}$Nótese que en un espacio de Hilbert de dimensión infinita esto implica que hay infinitas bolas unitarias abiertas disjuntas dentro de una bola de radio r si y solo si${\displaystyle r\geq 1+{\sqrt {2}}}$Por ejemplo, las bolas unitarias centradas en${\displaystyle {\sqrt {2}}e_ {j}}$, dónde${\displaystyle \{e_{j}\}_{j}}$es una base ortonormal, son disjuntos y están incluidos en una bola de radio${\displaystyle 1+{\sqrt {2}}}$centrado en el origen. Además, para${\displaystyle r<1+{\sqrt {2}}}$, el número máximo de bolas unitarias abiertas disjuntas dentro de una bola de radio r es$${\displaystyle \left\lfloor {\frac {2}{2-(r-1)^{2}}}\right\rfloor .}$$

Las personas determinan la cantidad de objetos esféricos de un diámetro dado d que se pueden empaquetar en un cuboide de tamaño${\displaystyle a\times b\times c}$.

Las personas determinan la altura mínima h de un cilindro con un radio R dado que empaquetará n esferas idénticas de radio r (< R ) . ^{[ 12 ]} Para un radio R pequeño, las esferas se organizan en estructuras ordenadas, llamadas estructuras columnares .

Las personas determinan el radio mínimo R que permitirá empaquetar n poliedros idénticos de volumen unitario de una forma dada. ^{[ 13 ]}

A las personas se les dan n círculos unitarios y deben empaquetarlos en el contenedor más pequeño posible. Se han estudiado varios tipos de contenedores:

• Empaquetamiento de círculos en un círculo : estrechamente relacionado con la dispersión de puntos en un círculo unitario con el objetivo de encontrar la mayor separación mínima, d _n , entre puntos. Se han demostrado soluciones óptimas para n ≤ 14 y n = 19 .
• Empaquetar círculos en un cuadrado : estrechamente relacionado con la dispersión de puntos en un cuadrado unitario con el objetivo de encontrar la mayor separación mínima, d _n , entre puntos. Para convertir entre estas dos formulaciones del problema, el lado del cuadrado para círculos unitarios será${\displaystyle L=2+2/d_{n}}$.

  

  Se han demostrado soluciones óptimas para n ≤ 30 .
• Empaquetar círculos en un rectángulo
• Empaquetamiento de círculos en un triángulo rectángulo isósceles : se conocen buenas estimaciones para n < 300 .
• Empaquetamiento de círculos en un triángulo equilátero : se conocen soluciones óptimas para n ≤ 15 y existen conjeturas para n ≤ 34. ^{[ 14 ]}

A las personas se les entregan n cuadrados unitarios y deben empaquetarlos en el recipiente más pequeño posible, donde el tipo de recipiente varía:

• Empaquetamiento de cuadrados en un cuadrado : Se han demostrado soluciones óptimas para n de 1-10, 14-16, 22-25, 33-36, 62-64, 79-81, 98-100 y cualquier entero cuadrado . El espacio desperdiciado es asintóticamente O ( a ^3/5 ) .
• Empaquetamiento de cuadrados en un círculo : Se conocen buenas soluciones para n ≤ 35 .

  

• Empaquetado de rectángulos idénticos en un rectángulo : El problema de empaquetar múltiples instancias de un solo rectángulo de tamaño ( l , w ) , permitiendo una rotación de 90°, en un rectángulo más grande de tamaño ( L , W ) tiene algunas aplicaciones, como la carga de cajas en paletas y, específicamente, el almacenamiento de pulpa de madera . Por ejemplo, es posible empaquetar 147 rectángulos de tamaño (137,95) en un rectángulo de tamaño (1600,1230).
• Empaquetar diferentes rectángulos dentro de un rectángulo : El problema de empaquetar múltiples rectángulos de diferentes anchos y alturas dentro de un rectángulo contenedor de área mínima (pero sin límites en el ancho o la altura del rectángulo contenedor) tiene una aplicación importante en la combinación de imágenes para crear una sola imagen de mayor tamaño. Una página web que carga una sola imagen de mayor tamaño suele renderizarse más rápido en el navegador que la misma página que carga varias imágenes pequeñas, debido a la sobrecarga que implica solicitar cada imagen al servidor web. El problema es NP-completo en general, pero existen algoritmos rápidos para resolver instancias pequeñas.