Newsgroup: it.hobby.enigmi
Titolo: Packing che passione

Qual e' il triangolo (qualunque) di area minima che contiene 4 cerchi di diametro unitario, senza sovrapposizioni?
 
Ciao
Livio

 diametro unitario, senza sovrapposizioni?
 
A me viene un'area di 9 + 6*sqrt(3).
 
Si può fare meglio?
 
M.
 
-- 
Per rispondermi via e-mail togli l'ovvio.

Mmm... Maurizio c'e' qualche cosa che non va. E' un'area esagerata per 4 cerchi di diametro 1.

 E' un'area esagerata per 4 cerchi di diametro 1.
 
Scusa, avevo letto "raggio unitario"! Poco male: basta dividere l'area
per 4...
 
9/4 + (3/2)*sqrt(3)


 9/4 + (3/2)*sqrt(3)
 
Questa volta il disegnino posso mettercelo io :-)
 
http://it.tinypic.com/view.php?pic=oi877c&s=8#.VYVIw9Ttmko
 
 
Ciao
Gabriele

Maurizio e GaS, mi sembra giusto, anche se non l'ho dimostrato. Ma adesso che voi 2 siete arrivati alla stessa conclusione... :-)

Forse anche la generalizzazione del problema e' interessante: per N=1 e N=3 e' banale, ma gia' per N=2 non lo e' piu'...

 Forse anche la generalizzazione del problema e' interessante: per N=1 e N=3 e' banale, ma gia' per N=2 non lo e' piu'...
 
In effetti N=2 già non è facile.
 
Ovviamente la posizione relativa dei 2 cerchi è obbligata, OO, manca di costruirci il triangolo intorno.
 
=====PRIMA SOLUZIONE====
 
La prima soluzione ovvia sarebbe quella di metterli all'interno di un triangolo isoscele con ogni cerchio tangente alla base e ad un lato del triangolo:
 
 /\
/OO\
 
Il problema diventa di trovare l'angolo alla base, chiamiamolo 2x, che minimizza l'area.
Con qualche calcolo si trova:
 
Area=(tan(2x)*(1+1/tan(x))^2)/4
 
e tale funzione ha un minimo per 2x=Pi/4 e quindi per un angolo alla base di 45°.
 
Il minimo si ha quindi per un triangolo 45°-45°-90° e vale
 
Area=3/2+sqrt(2)=2,914+
 
 
=====SECONDA SOLUZIONE====
 
Altra soluzione sarebbe di inserire i due cerchi sempre in un triangolo isoscele ma posizionati "verticalmente":
 
  ^
 /O\
/_O_\
 
 
Chiamando 2x l'angolo in alto si ha:
 
Area=((3/2+1/(2*sin(X)))^2)*tan(x)
 
 
=====ANALISI SOLUZIONI====
 
Ho graficato entrambe le soluzioni al variare di x:
 
https://goo.gl/ubleVo
 
 
- in blu il primo caso (0<x<Pi/4)
- in rosso il secondo caso  (0<x<Pi/2)
 
Si vede che il minimo si ha, anche se di poco, per il primo caso e quindi per la soluzione precedentemente trovata.
 
Si trovano soluzioni migliori?
 
Ciao
GaS

 Si trovano soluzioni migliori?
 
Io sono arrivato alle tue stesse conclusioni e non credo esistano
soluzioni migliori, anche se una dimostrazione generale va oltre la mia
pazienza. Mi chiedo se esista una dimostrazione di minimo "semplice"
visto che la soluzione (un triangolo equilatero isoscele) lo č.
 
Per n = 5 ci sono varie configurazioni possibili per i cerchi e non č
ovvio quale sia la migliore. Tuttavia ripetere i calcoli (piuttosto
noiosi) ogni volta non č particolarmente gratificante. Ci vorrebbe un
approccio euristico valido almeno per decidere quale sia la disposizione
"vincente" dei cerchi.


 pazienza.
 
La seconda soluzione può essere anche migliorata leggermente facendo "rotolare" il cerchio sotto fino a renderlo tangente ad uno dei lati obliqui e alzando quindi un po' la base (spero di essermi spiegato).
 
In questo modo, chiamando sempre 2x l'angolo in alto, si ha:
 
Area=tan(x)*(1/(2*sin(X))+cos(x)+1/2)^2
 
Ho sovrapposto tale curva alle precedenti pensando di aver migliorato la soluzione ma niente da fare: 
https://goo.gl/8fAyRK
 
 
La curva in verde è quella di nuova costruzione, per come è stata costruita migliora la soluzione rossa ma di veramente poco e purtroppo non migliora la blu :-(
 
Continuo a pensare che la soluzione ottimale sia dentro un triangolo scaleno e quindi ancora da trovare
 
ciao

GaS:
Continuo a pensare che la soluzione ottimale sia dentro un triangolo scaleno e quindi ancora da trovare 
 
---------
Non ci scommetterei. Il dualismo ha dato soluzioni simmetriche fin dai tempi dello Yin e dello Yang. 
Cmq bravo. Bello anche il link dei grafici che si puo' usare con lo smartphone, mio attuale limite.
Sto provando  N=7 con carta penna e smartphone. Anche lui interessante.
 
Ciao
Livio

 ovvio quale sia la migliore.
 
Infatti il  minimo (almeno per il momento) mi viene da una
configurazione inattesa: quattro cerchi ai vertici di un quadrato e il
quinto tangente a due di questi, a mo' di casetta.
 
Il triangolo minimo è isoscele con la base sul pavimento della casetta
mentre i lati obliqui sono tangenti ciascuno a una sola circonferenza.
Mi viene un'area minima di 6,533 che è di pochissimo inferiore a quella
che otterrei con un triangolo equilatero.


 Non ci scommetterei. Il dualismo ha dato soluzioni simmetriche fin dai tempi dello Yin e dello Yang. 
 
Come al solito hai ragione: ho inserito i due cerchi OO in un triangolo qualsiasi con angoli alla base 2x e 2y
 
 /\
/OO_\
 
l'area viene (una schifezza di funzione):
 
Area= 1/2((1/(2*tan(x))+1/(2*tan(y))+1)^2)sin(2x)sin(2y)/sin(pi-2x-2y)
 
Ho fatto minimizzare la funzione per x e per y a WolfranAlpha e mi trova il minimo per 2x=2y=pi/4 che è esattamente la soluzione già trovata
 
Se siete interessati qui il link: 
http://goo.gl/d9PRQk
 
 
Direi però che, a questo punto, abbiamo una dimostrazione del fatto che la soluzione trovata sia effettivamente minimale!
 
Ciao
GaS

Scusa, ma allargando i due cerchi del pavimento l'area non dovrebbe diminuire?


La soluzione per 6 cerchi mi sembra obbligata mettendoli a piramide all'interno di un triangolo equilatero: in questo modo abbiamo un triangolo equilatero di lato 2+sqrt(3) e quindi un'area di 6,031+
 
Togliamo un cerchio dei 6 ed abbiamo una soluzione per 5 cerchi con area sempre di 6,031+, sembra quindi questo il facile valore di partenza eventualmente da ottimizzare (ma ne dubito).
 
Ciao,
Gas
 

 eventualmente da ottimizzare (ma ne dubito).
 
Hai ragione, mi ero confuso sul valore di quest'area. Confermo allora
che le altre disposizioni che ho provato (5 in linea, 4 in linea + 1, la
casetta) danno valori dell'area più alti.
 
Certo che c'è un sacco di vuoto nella disposizione di area minima...


 Sto provando  N=7 con carta penna e smartphone. Anche lui interessante.
 
Questa la mia migliore disposizione per N=7:
 
http://s21.postimg.org/cco0bdpmu/sette_cerchi.jpg
 
 
Il valore dell'area (7,80887) non sarà precisissimo ma dovrebbe essere
vicino a quello vero.



Finalmente uno scaleno! :-) (N=4 era rettangolo)
 
Ciao
Livio

 vicino a quello vero.
 
Ecco un valore più preciso: 7,8061.



------------------------------------------------------
Io avrei trovato questo:
 
http://s29.postimg.org/gv71ewxuv/Packing7.png
 
 
Certo non sono proprio sicuro sicuro, il mio calcolo e' solo numerico...
ma magari qualcuno lo verifichera' (o falsifichera'). E' la Scienza! :-)
 
Ciao
Livio
 

 ma magari qualcuno lo verifichera' (o falsifichera').
 
A me la tua area viene 7,8030+ sicché ancora una volta vince il
triangolo isoscele! E io che ci speravo...



--------------------------------
confermo 7,803044+
Non ci resta che andare avanti, alla ricerca dello scaleno perduto. :-)


----------------------------------
Intanto c'e' questo isoscele N=8 da battere/verificare/falsificare :-)
 
http://s17.postimg.org/ky6qy909r/Packing8.jpg
 
 
... fatto con potenti mezzi. :-)
 


Questo si può battere con uno scaleno !


---------------------------------
"Io prima vedere cammello" [cit] :-)


-------------------------------------------------
Metodo empirico per N=11:  costo 5.50 euro :-)
 
http://s13.postimg.org/3m8ia13uf/Packing11.jpg
 
 
Ma... un software, un algoritmo... niente?
Se voi doveste fare un programma per trovare automaticamente la soluzione
ottimale, sapreste da che parte cominciare? :-)
 

 "Io prima vedere cammello" [cit] :-)
 
-----------------------
Questo? :-)
 
http://s23.postimg.org/sfnfmhemj/Packing8scaleno.jpg
 
 

 ottimale, sapreste da che parte cominciare? :-)
 
No :)
 
ciao,
Mauro

 
http://s23.postimg.org/sfnfmhemj/Packing8scaleno.jpg
 
 
Proprio lui!
 
http://s2.postimg.org/bfoznysg9/otto_cerchi.png
 
 
Che sia la volta buona dello scaleno?



-----------------------------------
Mi sembra che anche altri approcci finiscano per confluire in questa
soluzione. Comincerei a scommetterci.
 
Ciao
Livio
 


Purtroppo non posso partecipare a questo thread perchè conosco i record 
attuali. Questo ad es. si può migliorare.
 


------------------------------------------------
Anche questa volta non siamo stati originali, dunque! :-(
 
La tua conoscenza sullo stato dell'arte e' enciclopedica, Dario!
Io pensavo che il sito di Erich Friedman fosse la summa di tutto il 
sapere sull'argomento!
 
http://www2.stetson.edu/~efriedma/packing.html
 
 
Ciao
Livio
 

 
 
Difatti Livio ci sono... guarda
Circles in Arbitrary Triangles


------------------------------
Ostia! Sono proprio cecato! :-)