Kleinster Abstand

04.04.2007, 13:47

Sunwater

Kleinster Abstand

Hi...

ich habe ein Problem, bei dem ich nicht so einfach auf die Lösung komme.
Gegeben sind n verschiedene Punkte $\begin{eqnarray*} x_i \in \mathbb E^1 \end{eqnarray*}$
( leider weiß ich nicht, was dieses E bedeutet - ich denke mal eine Ebene )
Gesucht ist ein Punkt $\begin{eqnarray*} x^* \end{eqnarray*}$ , der von diesen n Punkten die kleinste Abstandssumme aufweist.

a) wie lautet die zugehörige Optimierungsaufgabe? ( gelöst )

b) bestimmen sie durch elementare Überlegungen die Lösung dieser Aufgabe

c) Formulieren sie ein äquivalentes lineares Optimierungsproblem, welches die Lösung der Ausgangsaufgabe liefert.

tja - bei b) - ich habe jetzt als Spezialfall für drei Punkte schon den Fermat-punkt gefunden. Wenn ich die Idee des Fermat-punktes jetzt verallgemeinern würde kommt folgendes raus:

die n Punkte bilden ja ein n-Eck. Der Lösungspunkt ist ein Punkt in diesem n-Eck, so dass zwischen je zwei Verbindungsgeraden zwischen den Punkt und den Ecken des n-Ecks ein Winkel von 360/n liegt.
( beim Fermatpunkt sind es ja 120 = 360/3 ).

leider habe ich keine Ahnung, wie Fermat erstmal auf die Idee gekommen ist, dass der Winkel immer 120 Grad sein muss... - deswegen kann ich auch meine Idee nicht belegen.

bei c) hab ich gar keine Ahnung, da wir erst mit Optimierung angefangen haben...

P.S. - ich wusste nicht wohin mit dem Thread - aber ist ja doch irgendwo Geometrie.

04.04.2007, 14:12

Auf diesen Beitrag antworten »

Zitat:

Original von Sunwater
( leider weiß ich nicht, was dieses E bedeutet - ich denke mal eine Ebene )

Ich denke schon, das solltest du erstmal klären. So ganz unwichtig erscheint mir das für die Lösung dieser Aufgabe nicht zu sein, in welchem Raum wir uns befinden...

06.04.2007, 14:05

Sunwater

Auf diesen Beitrag antworten »

ok - ich habe jetzt rausbekommen, dass $\begin{eqnarray*} \mathbb E^1 \end{eqnarray*}$ einfach nur eine Gerade sein soll.

Dann ist die Lösung von b) eigentlich ziemlich einfach.

Bei einer ungeraden Anzahl von Punkten $\begin{eqnarray*} x_1, ... , x_{2k+1} \end{eqnarray*}$ ist es der Punkt $\begin{eqnarray*} x_{k+1} \end{eqnarray*}$ , der die kleinste Abstandssumme hat.

bei einer geraden Anzahl an Punkten $\begin{eqnarray*} x_1, ... , x_{2k} \end{eqnarray*}$ ist jeder Punkt aus dem Intervall $\begin{eqnarray*} [x_k,x_{k+1}] \end{eqnarray*}$ eine Lösung.

jetzt weiß ich nur nicht ganz, was mit c) gemeint ist.

könnt ihr mir da nochmal weiterhelfen?

Neue Frage »

Antworten »

Kleinster Abstand

Verwandte Themen