Uninteressante Gitter

25/07/2008 - 00:01 von Jan Fricke | Report spam
Hallo Mitgefangene¹,
bei mir rotieren gerade die Gitter mit periodischem Muster:

Das Gitter G=Z^2 wird um den Nullpunkt gedreht, so dass ein zweites
Gitter H entsteht, das mit G mehrere gemeinsame Punkte hat. Das bedeutet
also, dass Sinus und Kosinus des Drehwinkels rational sind. Jene Werte
bekommt man aus a/c und b/c, falls (a,b,c) alle einfachen
pythagoràischen Tripel durchlàuft. Diese wiederum lassen sich erzeugen
durch ganze Zahlen u und v mit den Eigenschaften
(1) u > v >= 0,
(2) u und v haben verschiedene Paritàt und
(3) u und v sind teilerfremd.
Die Rotationsmatrix R hat dann die Gestalt
1 / p²-q² -2pq \
R = - | |,
p²+q² \ 2pq p²-q² /
und der Durchschnitt von G und H ist wieder ein Gitter, das von (p,q)
und (q,-p) erzeugt wird. Ein Fundamentalgebiet hat die Flàche f=p²+q².
Jetzt kommt vielleicht der erste überraschende Fakt: der Abstand eines
Punktes aus G von einem Punkt aus H hat stets die Form sqrt(d/f) mit
einer ganzen Zahl d. Damit làsst sich das ganze herrlich mit
Ganzzahlarithmetik programmieren:
(1) Bestimme zu jedem der f Punkte aus H die (maximal 5) Punkte aus G
mit Abstand <sqrt(2).
(2) Bestimme ein Matching zwischen den jeweils f Punkten aus G und H, so
dass der Maximalabstand minimal wird.

Das habe ich zunàchst per Hand gemacht, dann schrieb ich ein C-Programm,
welches ich aber wegwarf zugunsten eines Python-Programms. Diese
lieferte mir:

p | q | p²+q² | max Abstand | t(1) | t(2)
-+-+-++--+--
2 | 1 | 5 | sqrt(1/5) = 0.4472135955 | 0.0 | 0.0
5 | 2 | 29 | sqrt(13/29) = 0.669534063412 | 0.0 | 0.0
12 | 5 | 169 | sqrt(104/169) = 0.784464540553 | 0.0 | 0.01
29 | 12 | 985 | sqrt(673/985) = 0.826588610473 | 0.07 | 0.03
70 | 29 | 5741 | sqrt(4082/5741) = 0.843223549047 | 5.5 | 0.15
169 | 70 | 33461 | sqrt(24208/33461) = 0.850569875611 | 325.71 | 1.02

Der geneigte Leser wird in den p-q-Werten wahrscheinlich die
Nàherungsbrüche² von 1+sqrt(2) erkennen, was bedeutet, dass der
entsprechende Drehwinkel gegen 45° konvergiert. Man könnte jetzt
vermuten, dass der maximale Abstand gegen den völlig aus der Luft
gegriffenen Wert 0.8557 konvergiert. ;-)
Die Werte t(1) und t(2) sind die Zeiten in Sekunden, die das Programm
für die Schritte (1) und (2) braucht. Dabei fàllt auf, dass der erste
Schritt unheimlich viel mehr Zeit in Anspruch nimmt, als er sollte.
Deshalb meine Frage an das Auditorium³: Wieso geht das bei euch
schneller? 33461 Punktepaare sollten sich doch viel schneller zusammen
finden! Mein Algorithmus scheint O(f^2.3) zu brauchen, eigentlich
erwarte ich O(f). [Auf Wunsch sende ich das Programm per PM.]


Viele Grüße Jan





________
¹: Leute, die immer nur Gitter sehen ;-)
²: die abgebrochene Kettenbruchentwicklung, also [2], [2,2], [2,2,2],...
³: Man soll ja immer Fragen aufwerfen, damit das Interesse wach bleibt.
Falls einer bis zu dieser Stelle gekommen ist.
 

Lesen sie die antworten

#1 Jan Fricke
25/07/2008 - 09:55 | Warnen spam
Man sollte mitten in der Nacht keine Postings schreiben...

ich schrieb:
Diese wiederum lassen sich erzeugen
durch ganze Zahlen u und v mit den Eigenschaften
(1) u > v >= 0,
(2) u und v haben verschiedene Paritàt und
(3) u und v sind teilerfremd.


Statt (u,v) muss da natürlich (p,q) stehen.

p | q | p²+q² | max Abstand | t(1) | t(2)
-+-+-++--+--
2 | 1 | 5 | sqrt(1/5) = 0.4472135955 | 0.0 | 0.0
5 | 2 | 29 | sqrt(13/29) = 0.669534063412 | 0.0 | 0.0
12 | 5 | 169 | sqrt(104/169) = 0.784464540553 | 0.0 | 0.01
29 | 12 | 985 | sqrt(673/985) = 0.826588610473 | 0.07 | 0.03
70 | 29 | 5741 | sqrt(4082/5741) = 0.843223549047 | 5.5 | 0.15
169 | 70 | 33461 | sqrt(24208/33461) = 0.850569875611 | 325.71 | 1.02


408 |169 |195025 | sqrt(142088/...) = 0.853559022413 |37465.3 |10.89

Die Laufzeit verschlechtert sich sogar noch schlimmer als angenommen.
Das werde ich wohl noch mal genauer analysieren müssen.


Viele Grüße Jan

Ähnliche fragen