The authors of the comments are responsible for the content.

Re: Gepackte Smilies
von: matroid am: So. 13. Oktober 2002 19:33:31
\(\begingroup\)Wow, Friedel!

Und ich habe für n=5 zwei mögliche Anordnungen durchgerechnet.

5 Kugeln im Quadrat

Die rechte Anordnung entspricht dem oben vorgeschlagenen Muster.
Der Radius beträgt a*0.183 und die Flächenabdeckung 56.26% von a².

Bei der Anordnung links beträgt r = a*0.207 und die Abdeckung beträgt 67.38% von a².

[a ist die Seitenlänge des Quadrats.]

Der Rand ist für n=5 ein relativ großer Verlust.
Es ist also noch keineswegs sicher, daß die dichteste Packung in jeder Ebene das Optimum liefert.

Gruß
Matroid\(\endgroup\)
 
| Parent

 [Bearbeiten]

Re: Gepackte Smilies
von: Eckard am: Mo. 14. Oktober 2002 09:23:27
\(\begingroup\)Hallo Matroid,

schön, dass du dieses Thema auf den Matheplaneten gebracht hast. Vielleicht reift meine Theorie, warum sich manche Packungen so hartnäckig einer Optimierung widersetzen, etwas aus. Dazu muss allerdings einiges geschrieben werden. Mal sehen...

Hallo Friedel,

dein Ansatz kommt der Lösung bisher am nächsten. Und genau der übrige Platz ist das Problem. Kreispackungen sind seit einigen Jahren mein Hobby, daraus entstand z.B. Pack'o'mania!. Auch mein Freund, der Ungar Peter Szabo, ist ein eifriger Packer.

Womit wir es hier zu tun haben, sind geschichtete Gitterpackungen bzw. "Fast-Gitter-Packungen". Diese können durch zwei Parameter p und q wie folgt beschrieben werden:





p ist die Anzahl der (vertikalen) Spalten-1, q die Anzahl der (horizontalen) Reihen-1; im obigen Bild ist (p,q,n) = (2,3,6), wobei n die Anzahl der Kreise ist. Werden die charakteristischen Längen x, y wie im Bild eingeführt, müssen offensichtlich folgende Bedingungen gelten:

2 r + p x = y annehmen. Um jetzt die Dichte der Packung zu optimieren, setzen wir mal x/y = sqrt(3); dies entspricht dem hexagonalen Gitter (das bekanntermaßen die dichteste Packung in der Ebene darstellt). Mit der letzten Gleichung erhält man y=r und x=sqrt(3)*r. Machen wir nun entweder die erste oder zweite Ungleichung zu einer Gleichung, erhalten wir:

rp = 1/(sqrt(3)*p + 2),
rq = 1/(q+2).

Dies sind i.a. zwei verschiedene Radien, der größere muß ignoriert werden, damit eine nicht-überlappende Packung heraus kommt. Klar, dass für rp = rq oder q/p = sqrt(3) ein hexagonales Gitter entsteht, wegen der Irrationalität von sqrt(3) kann es aber solch eine Packung nicht geben.

Nun sind zwei Fälle möglich:

i) rp : Ein "Auffüllen" des Quadrats von unten führt auf eine sog. kondensierte Packung mit etwas "Luft" über dem oberen Rand (das ist genau der von Friedel beschriebene Fall). Man kann nun die horizontalen Schichten anheben bis sie den oberen Rand erreichen; dabei vergrößern sich die Kreise natürlich. Das Interessante hierbei ist, dass die Struktur der Packung beim Anheben nicht zerstört wird, ich nenne sie daher reihenartige Packung. Hier gilt:

r = gamma/(2*(1+gamma)) > rp mit gamma = sqrt(1/p^2 + 1/q^2).




Die beiden obigen Bilder verdeutlichen dies.

ii) rq : Hier ist immer am rechten Rand des Quadrats etwas "Luft" und wir können die einzelnen "Säulen" in sich nach rechts verschieben (s. unten stehende Bilder). Die Größe der Kreise bleibe dabei zunächst unverändert. Aufgrund dieser Struktur nenne ich diese Packungen spaltenartige Packungen.




Will man jetzt die Kreise vergrößern, können sie sich sowohl nach links als auch nach rechts verschieben: ein typischer Fall von Frustation. Genau das macht die spaltenartigen Packungen so problematisch. (Die 68er Packung ist eine solche!)

Soviel erstmal für heute. Morgen schreibe ich noch etwas zu ee-, eo-, oe- und oo-Packungen, wen es interessiert.

Gruss Eckard\(\endgroup\)
 
| Parent
 [Bearbeiten]

Re: Gepackte Smilies
von: Eckard am: Mo. 14. Oktober 2002 11:09:29
\(\begingroup\)Hier noch ein Bild (mein bestes bisher), das zeigt, dass die 68er Packung tatsächlich eine spaltenartige ist:





Die gelben Kreise sind solche, die fest von umgebenden Kreisen "eingespannt" sind, blaue haben noch Freiheitsgrade zum Verschieben und rote sind völlig frei. Sobald noch "blaue Kreise" vorhanden sind, ist dies m.E. ein Zeichen dafür, dass die Packung noch nicht optimal ist.

Hier nun ist es absolut schwer, die Kreise so zu "schütteln", dass nur gelbe und ggf. rote Kreise übrigbleiben, wie dies in anderen Packungen der Fall ist. Erschwerend kommt hinzu, dass diese Packung eine ee-Packung ist (diese haben in allen vier Ecken einen Kreis), doch dazu morgen mehr.

Gruss Eckard\(\endgroup\)
 
| Parent
 [Bearbeiten]

Re: Gepackte Smilies
von: matroid am: Mo. 14. Oktober 2002 20:23:08
\(\begingroup\)Hallo Eckard,

eine Freude Dich hier zu sehen! Ja, das Thema ist sehr dankbar für Versuche, wenn auch - wie es nach Deinen Erläuterungen scheint - undankbar, wenn es um klare Ergebnisse geht.

Ich habe mir Deine packomania angesehen. Ich vermute, Du hast n=68 als Aufgabe gestellt, weil das die kleinste Anzahl ist, bei der noch viele blaue Kreise in der Anordnung sind.

Ist das nicht-Vorhandensein von blauen Kreisen ein Kriterium für 'Nicht-Verbesserbarkeit' einer Lösung (sofern die gelben und roten Kreise nicht unnötig klein sind)?

Wie eine Tabelle von Dir zeigt, ist 68 auch ein lokaler Höhepunkt der realisierten density. Das ist aber eigentlich klar, denn es besteht die Möglichkeit zur Anordnung in 5 Spalten zu 8 und 4 Spalten zu 7.
Für diese lokalen Spitzenwerte gibt es doch vermutlich eine kombinatorische Erklärung.

Offensichtlich geht die erreichbare density mit wachsendem n und einhergehend fallendem Radius allmählich gegen 100%. Hat schon mal jemand eine obere Abschätzung für die erreichbare density gefunden - eine die etwas aussagt?

Ich bin gespannt, wie es weitergeht.

Viele Grüße
Matroid\(\endgroup\)
 
| Parent
 [Bearbeiten]

 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2022 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]