Quantos biscoitos na caixa de biscoitos? - Estrelas lado a lado

Com a temporada de férias chegando, decidi fazer algumas estrelas de canela . Isso foi divertido (e o resultado foi saboroso), mas meu nerd interior se encolheu quando coloquei a primeira bandeja de estrelas na caixa e elas não cabiam em uma camada:

Quase! Existe uma maneira de eles se encaixarem? Quão bem podemos ladrilhar estrelas, afinal? Dado que estas são estrelas regulares de seis pontas, certamente poderíamos usar as bem conhecidas inclinações hexagonais como uma aproximação, assim:

^{Desarrumei o do canto superior direito, gritos.}

Mas isso é ótimo? Há muito espaço entre as dicas.

Por essa consideração, vamos nos restringir a caixas retangulares e estrelas regulares de seis pontas, ou seja, existem trinta graus (ou ) entre todas as dicas e seus cantos vizinhos. As estrelas são caracterizadas pelo raio internorieraio externoro:$\frac{\pi}{6}$$r_i$$r_o$

^{[ fonte ]}

Observe que temos hexágonos para $r_i = \frac{\sqrt{3}}{2} \cdot r_o$$r_i = \frac{1}{\sqrt{3}} \cdot r_o$$\frac{r_i}{r_0} \in \Bigl[\frac{1}{\sqrt{3}}, \frac{\sqrt{3}}{2}\Bigr]$

$r_i \approx 17\mathrm{mm}$$r_o \approx 25\mathrm{mm}$

O que é um mosaico ideal para estrelas, como caracterizado acima? Se não houver melhor mosaico estático, existe um algoritmo para encontrar um bom com eficiência?

Deixe-me responder sua pergunta parcialmente para o caso do hexagrama.

Você pode fazer o seguinte lado a lado

$\hskip1.2in$

Com isso, você cobrirá 12/14 = 6/7 do plano (conte os triângulos no quadrilátero tracejado).

Isso é ótimo? Eu acho que sim. Embora eu não esteja dando uma prova, apresentarei alguns argumentos. Pode-se perguntar como podemos preencher o espaço (triângulo) entre os espinhos pontudos. No ladrilho acima, preenchemos metade dele. Podemos fazer melhor?

$\hskip20mm$

O gráfico dessa função se parece com isso e mostra que nossa intuição estava certa.

$\hskip30mm$

o seguinte não é oferecido como um ataque definitivo ou específico / superior a esse problema possivelmente inesperadamente complexo, mas como ângulos científicos / teóricos adicionais / estudos gerais ainda não abordados até agora.

1 ^r nesta área geral é conhecido / classificados como "embalagem bin" e este é um caso 2d. existem algumas provas famosas da matemática que estão relacionadas, por exemplo, o caso 3d da investigação de Keplers sobre empacotamento de esferas, que foi um problema aberto por séculos e "recentemente" resolvido com a prova de computador de Hales. Um exemplo de caso 2D usado diariamente na indústria é para otimizar os layouts de chips. obviamente, isso é diferente do problema, mas pode apontar para a complexidade desses tipos de problemas. por exemplo, não parece haver nenhuma teoria que exija / indique que um caso 2D seria mais simples que um caso 3D. Observe também que um limite retangular simples não ajuda a simplificar a solução, a não ser, digamos, um limite poligonal.

poderia haver uma solução analítica possível se algum tipo de definição / esquema básico de "ladrilhos regulares" fosse dado na declaração do problema, como colocação em uma grade etc., nesse caso as equações de cálculo podem ser derivadas e a localização ideal.

as condições do problema (talvez contra-intuitivamente) não parecem levar a uma solução ótima analítica. isso pode surpreender alguns problemas, mas muito semelhantes, de ladrilhar o avião são indecidíveis (esse foi um resultado famoso anos atrás e há muitas referências e até pesquisas em andamento). uma diferença fundamental entre os problemas decidíveis (solucionáveis ​​/ analíticos) e indecidíveis é se o ladrilho é "regular". o problema acima refere-se a "estrelas regulares", mas não a "mosaicos regulares". a outra resposta atual assume um tipo de ordem ou ordem regular, mas observe que mesmo definir "ordem regular" pode ser muito complicado formalmente / matematicamente.

problemas como esse são geralmente bastante passíveis de algoritmos genéticos . esse algoritmo pode encontrar pacotes "muito bons" que dificilmente serão aprimorados e talvez alguns limites possam ser colocados em sua otimização por métodos muito engenhosos (ou seja, devem estar dentro de um pequeno percentual de erro do ideal), mas não podem provar nenhuma são ótimos.

aqui estão algumas referências encontradas geralmente aplicáveis ​​diretamente:

• exemplo de uso de algoritmos genéticos. Em algoritmos genéticos para empacotamento de polígonos / Jacobs

• Algoritmos para problemas geométricos de empacotamento e dimensionamento Tese de doutorado / Michael Formann 1992, 92p, sec 3.6 Escala de objetos x-monótonos em forma de estrela p30

• ALGORITMO DE EMBALAGEM GEOMÉTRICA PARA ESFERAS ARBITRÁRIAS / ARFATH PASHA 2003 Tese de graduação 87p

• esta pergunta stackexchange também está próxima. empacotando polígonos arbitrários dentro de um limite arbitrário . é para limites arbitrários

Embora esse problema em particular provavelmente não tenha sido estudado, tais perguntas foram feitas por Laszlo Fejes Toth e são conhecidas como problemas de empacotamento. Eu recomendo fortemente o terceiro capítulo do livro de Pach-Agarwal .