Abstandsminimierung komplex < Abbildungen < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 02:04 Fr 08.08.2008 | | Autor: | seson |
Hallo
ich habe ein Problem, das ich nicht lösen kann. Ich habe eine Menge von Punkten mit festen Positionen. Allerdings können alle Punkte je um den gleichen Vektor verschoben werden. Außerdem habe ich meine Menge von Kreisen, jeder hat einen anderen Radius bzw. Mittelpunkt. Jeder Punkt der 1. Gruppe gehört zu einem Kreis der 2. Gruppe.
Ziel ist es, dass jeder Punkt in seinem Kreis liegt. D.h. die Frage ist, kann man alle Punkte gleichzeitig so verschieben, dass sie alle in ihren Kreisen liegen?
Ganz offensichtlich gibt es nicht für jede Belegung eine Lösung. Ich würde aber gerne wissen, wie man darauf kommt, dass es eine Lösung gibt.
Mein Lösungsansatz geht so:
Einen ersten Punkt direkt im ersten Kreis platzieren, d.h. die Gruppe aller Punkte so verschieben.
Dann über den Rest iterieren und jeweils die Punktegruppe so verschieben, dass der aktuelle Punkt gerade in seinem Kreis liegt.
Allerdings reicht es manchmal nicht, das einmal zu machen, sondern man muss das eventuell ein paar Mal machen, also immer wieder alles verschieben. Ich hätte gerne eine definitive Form, weil es so ziemlich nur langsam geht.
Ich habe diese Frage auch in folgenden Foren auf anderen Internetseiten gestellt:
http://www.onlinemathe.de/forum/Menge-von-Punkten-mit-Menge-von-Kreisen-decken
Dort hat aber keiner geantwortet.
Grüße
Sebastian
|
|
| |
|
Dass noch niemand geantwortet hat, liegt vielleicht an der
doch etwas komplexen Fragestellung, die ich auch noch nicht
recht durchschaue. Was ist fix, was ist verschiebbar und wie,
was meinst du mit Iterationen etc.
Kann man die Frage etwa so veranschaulichen: Man hat zwei
transparente Folien. Auf der einen sind n Punkte [mm] P_1, P_2,.... P_n
[/mm]
markiert, auf der anderen n Kreise [mm] k_1, k_2, [/mm] .... [mm] k_n.
[/mm]
Nun soll man die beiden Folien so aufeinander legen, dass
jeder Punkt [mm] P_i [/mm] in den entsprechenden Kreis [mm] k_i [/mm] zu liegen
kommt .... (oder so ähnlich - wie gesagt, ich verstehe die
Aufgabe noch nicht; aber vielleicht kannst du die exakte
Fragestellung mit solchen oder ähnlichen Bildern beschreiben)
Gruß
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:13 Fr 08.08.2008 | | Autor: | seson |
Dein Beispiel mit den beiden transparenten Folien trifft es genau. Dabei sind allerdings zwei Modi zu unterscheiden:
1) Die Folien dürfen jeweils nur entlang ihrer Seiten oder diagonal verschoben, nicht aber gedreht werden.
2) Die Folien dürfen auch beliebig gedreht werden.
|
|
|
| |
|
> Dein Beispiel mit den beiden transparenten Folien trifft es
> genau. Dabei sind allerdings zwei Modi zu unterscheiden:
>
> 1) Die Folien dürfen jeweils nur entlang ihrer Seiten oder
> diagonal verschoben, nicht aber gedreht werden.
>
> 2) Die Folien dürfen auch beliebig gedreht werden.
O.K., habe ich es also richtig interpretiert, wenn bei der
Ausgangslage jeder Punkt [mm] P_i [/mm] auf der entsprechenden
Kreislinie [mm] k_i [/mm] liegt und dann eine Bewegung (entweder
eine reine Translation in beliebiger Richtung aber ohne
Drehung oder als 2.Variante eine Drehung um ein beliebiges
Rotationszentrum) gefragt ist, welche jeden der n Punkte [mm] P_i [/mm]
vom Rand seines Kreises [mm] k_i [/mm] in dessen Inneres (ohne Rand)
befördert ?
Dann gibt es sicher Ausgangslagen, bei denen dies mit oder ohne
Drehung unmöglich ist, zum Beispiel dann, wenn es zwei einander
nicht überlappende oder umschliessende Kreise gibt und die beiden
entsprechenden Punkte gerade die kürzeste (oder die längste)
Verbindungsstrecke zwischen den beiden Kreisen markieren.
Um die vorliegenden Daten darzustellen, wird man sinnvoller-
weise für jedes Paar Kreis/Punkt 4 Koordinaten benützen:
die kartesischen Koordinaten [mm] xM_i, yM_i [/mm] des Kreismittelpunktes
und "lokale Polarkoordinaten" [mm] r_i, \varphi_i [/mm] für den Radius und
für die Lage des Punktes [mm] P_i [/mm] auf dem Kreis [mm] k_i.
[/mm]
Die Suche nach solchen Fällen ohne Lösung, wie ich sie oben
beschrieben habe, sollte damit relativ leicht bewerkstelligt
werden können. Dann bleibt aber noch die Frage, ob es, wenn
kein Konflikt dieser speziellen Art vorliegt, tatsächlich
immer eine Lösung gibt, und wie man eine solche konkret
vorlegen kann.
LG
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 08:48 Fr 08.08.2008 | | Autor: | abakus |
> Hallo
>
> ich habe ein Problem, das ich nicht lösen kann. Ich habe
> eine Menge von Punkten mit festen Positionen. Allerdings
> können alle Punkte je um den gleichen Vektor verschoben
> werden. Außerdem habe ich meine Menge von Kreisen, jeder
> hat einen anderen Radius bzw. Mittelpunkt. Jeder Punkt der
> 1. Gruppe gehört zu einem Kreis der 2. Gruppe.
>
> Ziel ist es, dass jeder Punkt in seinem Kreis liegt. D.h.
> die Frage ist, kann man alle Punkte gleichzeitig so
> verschieben, dass sie alle in ihren Kreisen liegen?
>
> Ganz offensichtlich gibt es nicht für jede Belegung eine
> Lösung. Ich würde aber gerne wissen, wie man darauf kommt,
> dass es eine Lösung gibt.
Suche dir von allen Kreisen den kleinsten heraus und fahre mit dem zugehörigen Punkt den Rand dieses Kreises ab. Damit hast du das Gebiet abgesteckt, in dem dieser Punkt liegen muss.
Da alle Punkte miteinander gekoppelt sind, zeichnen alle anderen Punkte bei dieser Beweigung ebenfalls diesen Kreis an ihrer jeweiligen Position mit.
Die Punktbelegung existiert nicht, wenn auch nur einer der so gezeichneten kleinsten Kreise vollständig außerhalb des ihm zugeordneten Kreises liegt.
Sie existiert mit Sicherheit, wenn alle kleinsten Kreise vollständig im jeweils dem Punkt zugeordneten Kreis liegen.
Sie existiert möglicherweise, wenn sich einige kleinste Kreise mit den zugeordneten Kreisen nur teilweise überschneiden. Dazu müsste man aus jedem Kleinkreis das Schnittgebiet mit seinem zugeordneten Kreis herausnehmen und alle Schnittgebiete übereinanderlegen. Dann schaut man, ob alle übereinander gelegten Schnittgebiete einen gemeinsamen Punkt haben.
Heureka!
Man kann doch diese ganzen Überdeckungsgebiete durch jeweils eine Koordinatentransformation in zum Koordinatenursprung verschieben (d.h. eigentlich müssen die ganzen Kleinkreise mit dem Mittelpunkt in den Ursprung, und jeder zugehörige größere Kreis muss die Bewegung seines kleineren Kreises mitmachen. Sozusagen ein Sternmarsch aller Kreise Richtung Ursprung.) Dort sieht man, ob sich die großen Kreise überschneiden.
Gruß Abakus
>
> Mein Lösungsansatz geht so:
> Einen ersten Punkt direkt im ersten Kreis platzieren, d.h.
> die Gruppe aller Punkte so verschieben.
> Dann über den Rest iterieren und jeweils die Punktegruppe
> so verschieben, dass der aktuelle Punkt gerade in seinem
> Kreis liegt.
>
> Allerdings reicht es manchmal nicht, das einmal zu machen,
> sondern man muss das eventuell ein paar Mal machen, also
> immer wieder alles verschieben. Ich hätte gerne eine
> definitive Form, weil es so ziemlich nur langsam geht.
>
> Ich habe diese Frage auch in folgenden Foren auf anderen
> Internetseiten gestellt:
>
> http://www.onlinemathe.de/forum/Menge-von-Punkten-mit-Menge-von-Kreisen-decken
>
> Dort hat aber keiner geantwortet.
>
> Grüße
> Sebastian
|
|
|
| |
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 17:18 Fr 08.08.2008 | | Autor: | seson |
Danke für diese Antwort. Die Idee mit dem kleinsten Kreis zu beginnen ist auf jeden Fall eine sehr gute für die beiden aufgezeigten definitiven Aussagen. Mein Problem ist natürlich die Aussage "möglicherweise".
Da ich einen Algorithmus implementieren muss, kann ich nur diskret denken. Das Abfahren des Rands eines Kreises könnte ich somit durch eine Formel ausdrücken. Dann müsste ich dies zu einer Formel führen, die zwei sich überdeckende Kreise ausdrückt. Von all den Ergebnissen dieser Überdeckungen müsste noch einmal die Schnittmenge genommen werden.
Rein logisch stellt sich mir die Lösung dar. Das Problem ist, dass ich nicht weiß, wie ich einen Computer eine solche verkettete Formel automatisch lösen lassen kann.
Grüße,
Sebastian
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:21 Fr 08.08.2008 | | Autor: | seson |
Ich habe die Fälligkeit aus Versehen bei den voreingestellten 24 Studen gelassen, so dass der Artikel jetzt leider in rot auftaucht. Weiter habe ich auch keinen Editieren-Button gefunden.
Ich bitte um Verzeihung.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:31 Fr 08.08.2008 | | Autor: | pelzig |
> Ich habe die Fälligkeit aus Versehen bei den
> voreingestellten 24 Studen gelassen, so dass der Artikel
> jetzt leider in rot auftaucht.
Das hat nix mit der Fälligkeit zu tun. der Artikel erscheint "rot" (ich nehme an du meinst das kleine rote Quadrat) wenn es offene Fragen gibt und die Fälligkeit noch nicht abgelaufen ist-
>Weiter habe ich auch keinen
> Editieren-Button gefunden.
Du kannst eigene Artikel und Mitteilungen Editieren indem du bei der entsprechenden Nachricht unten rechts auf "reagieren" gehst, auf der nächsten Seite müsste es als Option "Für dich, den Autor, bearbeite den Nachrichtentext" oder so ähnlich geben. Dort kann man auch die Fälligkeit nachträglich noch verändern.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:30 Mo 11.08.2008 | | Autor: | PeterB |
Erst mal: Entschuldigung, ich habe gerade ein Problem mit der Foren-Technologie, daher ist meine Antwort eine Mitteilung.
Ich kann dir einen endlichen Algorithmus beschreiben, der sicher das Ergebnis liefert, allerdings ist er nicht besonders gut: Die Komplexität wächst mit der Zahl $n$ der Punkte hoch 4.
Genauer gebe ich endlich viele [mm] (~$n^3$) [/mm] Vektoren an, von denen entweder einer ein Verschiebungsvektor der gesuchten Form ist, oder das Problem ist für die gegebenen Werte nicht lösbar.
Die Idee ist wie so oft in der Mathematik: Ich mache mehr als gefordert ist, und dadurch wird das Problem einfacher: Ich suche nicht einen beliebigen Vektor, so dass es passt, sondern den Vektor $v$, so dass folgender Wert minimal wird:
[mm] $d(v):=max_i(|x_i+v-M_i|/r_i)$ [/mm]
Mit: [mm] $x_i$: [/mm] Die Punkte, [mm] $M_i$: [/mm] Die Mittelpunkte der Kreise.
Das heißt wir minimieren den maximale Abstand zu den Mittelpunkten relativ zum Radius. Man überlegt sich leicht, dass $v$ das Problem genau dann löst, wenn [mm] $d(v)\leq [/mm] 1$.
Was helfen uns diese Überlegungen? Nun zunächst stellen wir fest, dass [mm] $d_i(v)=|x_i+v-M_i|/r_i$ [/mm] außerhalb von [mm] $v=M_i-x_i$ [/mm] kein lokales Minimum hat.
Sei nun [mm] $v_0$ [/mm] die Stelle, an der $d(v)$ sein globales Minimum annimmt. Der Fall [mm] $d(v_0)=0$ [/mm] kann nur auftreten, wenn die Verschiebung von [mm] $x_1$ [/mm] nach [mm] $M_1$ [/mm] alle [mm] $x_i$ [/mm] nach [mm] $M_i$ [/mm] verschiebt, diesen Fall müssen wir ausschließen.
Wir behaupten nun: [mm] $d_i(v_0)=d(v_0)$ [/mm] für mindestens zwei verschiedene $i$. Darüber hinaus sind wir in einem von zwei Fällen:
1) [mm] $d_i(v_0)=d(v_0)$ [/mm] gilt sogar für 3 verschiedene $i$ oder
[mm] 2)$d_i(v_0)=d(v_0)=d_j(v_0)$ [/mm] für [mm] $i\neq [/mm] j$ und [mm] $v_0$ [/mm] ist unter den Vektoren $v$ mit [mm] $d_i(v)$ [/mm] minimal.
Für je drei Punkte [mm] $x_i,x_j,x_k$ [/mm] gibt es maximal 2 Vektoren $v$ so dass [mm] $d_i(v)=d_j(v)=d_k(v)$ [/mm] und für je zwei Punkte gibt es nur einen Vektor, der die Bedingung 2 erfüllt.
Der Beweis ist nicht so furchtbar schwierig, im wesentlichen ein Stetigkeitsargument. Man muss allerdings die konkrete Form der Mengen [mm] $\{v|d_i(v)=d_j(v)\}$ [/mm] verwenden.
Diese Mengen sind Geraden, falls [mm] $r_i=r_j$, [/mm] und sonst Kreise. Man bezeichnet sie als sogenannte "Apollonische Kreise". Vielleicht schaust du dir mal eine der Quellen dazu an.
Da mir nicht so klar ist ob dir der Algorithmus hilft, höre ich einfach mal auf. Wenn du noch Fragen zum Beweis oder zur konkreten Konstruktion der Vektoren hast, frag einfach noch mal konkret.
Gruß
Peter
|
|
|
|
