Verbindungslaengen im Einheitsquadrat

13/03/2009 - 12:31 von Thomas Nordhaus | Report spam
Hallo -
mich interessiert folgendes Problem: Gesucht seien diejenigen
n-elementigen Teilmengen M des Einheitsquadrats Q in der euklidischen
Ebene, bei denen die Lànge L des kürzesten verbindenden Polygonzugs
maximal wird. Diese Lànge bezeichne ich mal mit L_n. Für n=2 ist
offensichtlich L_n = sqrt(2) und M besteht aus zwei diametralen Eckpunkten.

Für n=3 wird es schon interessanter. Ich habe mich davon "überzeugt",
dass L_3 = 1 + (1/2)*sqrt(5) = ca. 2.12 ist. Das zugehörige
(gleichschenklige) Dreieck besteht dabei aus zwei Ecken des Quadrats
sowie dem Mittelpunkt der gegenüberliegenden Seite. Zwei weitere
Kandidaten, die ich ausschlieen konnte waren:

I) Das rechtwinklige Dreieck mit Seitenlàngen 1,1, sqrt(2). Dabei ist L=2.

II) Das größte eingeschriebene gleichseitige Dreieck. Dieses hat die
Seitenlànge 1/cos(15°) und damit L = 2/cos(15°) = ca. 2.07.

Überraschend finde ich, dass die entsprechenden Werte für L so eng bei
einander liegen. "Intuitiv" hàtte man vllt. angenommen, dass das Maximum
im Fall I) angenommen wird, d.h. auf den *Ecken* des Quadrats. Dies ist
z.B. so, wenn man das Problem auf den Einheitswürfel im IR^3
verallgemeinert. Dort ist L_3 = 2*sqrt(2), das zugeh. Dreieck ist
gleichseitig und die Eckpunkte liegen auf drei Ecken des Würfels.

Das aber nur am Rande! Meine Fragen wàren:
A) Stimmt meine Überlegung oben - oder habe ich noch einen Fall
vergessen, d.h. L_3 > 1 + 0.5*sqrt(5). (Hoffentlich nicht ;) ).

B) Gibt es einen Kalkül, bei dem man die L_n effizienter berechnet als
durch viele individuelle, komplizierte Fallunterscheidungen? Für n=4
habe ich mich z.B. "überzeugt" dass hier L_4 = 3 und als Konfiguration
gerade die Eckpunkte des Quadats sind. Und bei 5 Punkten sollte L_5 =
3+sqrt(2)/2 sein, usw. ...

Thomas
 

Lesen sie die antworten

#1 Thomas Nordhaus
13/03/2009 - 13:42 | Warnen spam
Thomas Nordhaus schrieb:
Für n=4
habe ich mich z.B. "überzeugt" dass hier L_4 = 3 und als Konfiguration
gerade die Eckpunkte des Quadats sind. Und bei 5 Punkten sollte L_5 =
3+sqrt(2)/2 sein, usw. ...



Korrektur: L_5 = 2+sqrt(2).

Thomas Nordhaus

Ähnliche fragen