Minkowski-Summe < Sonstiges < Hochschule < Mathe < Vorhilfe
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 16:26 Mo 12.06.2006 | | Autor: | Galois |
Hallo Bastiane! ![[hand]](/images/smileys/hand.gif "[hand]")
Wir haben uns ja lange nicht mehr gelesen!
Ich denke, Induktion über die Seitenzahl des Polygons (worüber auch sonst?) sollte funktionieren.
Ich gebe Dir mal eine anschauliche Lösung, die Details kannst Du dann ja selbst ausarbeiten.
Die Idee ist folgende: Angenommen, das Polygon mit n Ecken stellt den Grundriß eines Zimmers dar. Unsere Aufgabe ist dann, eine streckenförmige oder dreieckige Staubsaugerdüse zu konstruieren, mit der wir - allein durch Parallelverschiebungen! - in alle Ecken kommen, und so daß die Menge der hierfür erforderlichen Parallelverschiebungen ein Polygon mit n-1 (!) Ecken bilden.
Wie gehen wir hierfür vor? Wir nehmen uns das Polygon, legen es so vor uns auf den Tisch, daß die kürzeste Seite (oder eine der kürzesten Seiten) unten & waagerecht zu liegen kommt. Nehmen wir jetzt zunächst diese Seite als Staubsauger!
Wir sehen dann leicht, daß, wenn wir mit dieser Düse die Wände des Polygons entlangsaugen, ein auf dieser Düse fixierter Punkt ein n-1 Eck beschreibt. Ferner kommen wir mit unserem Frühlingsputz in alle Ecken - es sei denn, es gibt eine einzelne, die die Spitze des Polygons bildet (d. h. mit größter Entfernung zu unserer anfänglichen Grundkante).
Um diese Ecke auch noch sauber zu bekommen, müssen wir aus unserer Düse - bei Beibehaltung der bisherigen Kante als Grundlinie - ein richtiges Dreieck formen, das mit seiner Spitze gerade jene Spitze des Polyeders nachbildet. Glücklicherweise gelten für diese neue Düse die zuvor gemachten Aussagen weiterhin.
Damit ist der Induktionsschritt komplett. 
Grüße,
Galois
P.S.: Macht ihr das gerade in Praktischer Mathematik? 
![[]](/images/popup.gif) Bonner Matheforum
|
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 00:20 Di 13.06.2006 | | Autor: | Bastiane |
Hallo Galois!
> Wir haben uns ja lange nicht mehr gelesen!
Ja, ich glaube, ich habe lange keine Frage mehr gestellt, und vor allem schon seit noch längerer Zeit nur sehr wenige Fragen.
Erstmal schon mal vielen Dank für deine Antwort. Und dann auch noch so eine schön erzählte - erinnert mich an Pauls Antwort mit dem Buchhalter und eine mit einem Kamin. (ich glaub, mit letzterer wollte er mir ein Vektorfeld oder so etwas ähnliches erklären. )
> Ich denke, Induktion über die Seitenzahl des Polygons
> (worüber auch sonst?) sollte funktionieren.
Gut - ich hatte überhaupt keine Ahnung. ![[haee]](/images/smileys/haee.gif "[haee]") [mm] \to [/mm] ![[lichtaufgegangen]](/images/smileys/lichtaufgegangen.gif "[lichtaufgegangen]")
> Ich gebe Dir mal eine anschauliche Lösung, die Details
> kannst Du dann ja selbst ausarbeiten.
Das habe ich jetzt mal versucht. Kannst du (oder natürlich auch ggf. jemand anders) bitte nochmal drübergucken? Ich kann das noch nicht ganz so mit dem Abstrahieren (heißt das so?). Außerdem habe ich fast nur Text - ist das ok, oder kann/muss man das noch mehr in "Formeln" bringen?
Beweis durch Induktion nach n:=Anzahl der Kanten des Polygons
Induktionsanfang:
n=3
Lege das Dreieck P in den Ursprung und [mm] $s:=\mbox{die kürzeste Kante}$ [/mm] irgendwo hin. Dann gilt: [mm] $P=P\oplus [/mm] s$ [mm] \to [/mm] fertig.
Man braucht doch immer ein "Bezugssystem" oder? Oder kann ich einfach schreiben, dass [mm] $P=P\oplus [/mm] s$ ohne zu sagen, dass P im Ursprung liegt und s irgendwo? (Außerdem ginge es auch anders: s in den Ursprung und P irgendwo, oder?)
Induktionsvoraussetzung:
Jedes Polygon mit n Ecken ist darstellbar als Minkowski-Summe von Dreiecken und Strecken.
Induktionsschritt: [mm] $n\to [/mm] n+1$
Sei s die kürzeste Seite des Polygons P und P' das Polygon, das aus Parallelverschiebungen von s entlang des Randes von P ensteht.
(Ist das klar, was damit gemeint ist? Oder kann man das noch anders formulieren? Werde aber auf jeden Fall eine Skizze dazu machen )
P' besteht offenbar aus n-1 Ecken und somit auch n-1 Kanten.
(Ist das trivial? Oder muss ich das auch noch irgendwie beweisen?)
Fall 1: Die gegenüberliegende Seite von s ist parallel zu s
[mm] \to $P=P'\oplus [/mm] s$(wiederum mit s im Ursprung und P' irgendwo oder umgekehrt) [mm] \to [/mm] fertig
Fall 2: Die gegenüberliegende Seite von s ist nicht parallel zu s
[mm] \to [/mm] Bei der Parallelverschiebung bleibt eine "Spitze" übrig. Diese nennen wir s'. Setzen wir diese Spitze auf die Kante s - es einsteht ein Dreieck s'' - und machen noch einmal unsere Parallelverschiebung, so entsteht das selbe Polygon P' wie vorher, aber es bleibt keine Spitze mehr übrig.
[mm] \to $P=P'\oplus [/mm] s''$(wiederum mit s'' im Ursprung und P' irgendwo oder umgekehrt) [mm] \to [/mm] fertig
Ach ja, ich sollte vielleicht noch erwähnen, dass für P' die Aussagen natürlich nach Induktionsvoraussetzung gilt.
Es muss nicht perfekt sein - aber kann man das so aufschreiben???
> P.S.: Macht ihr das gerade in Praktischer Mathematik?
Nein ![[kopfschuettel]](/images/smileys/kopfschuettel.gif "[kopfschuettel]") , in dieser netten Vorlesung. Und die gehört meines Wissens zur theoretischen Informatik.
Viele Grüße
Bastiane
![[cap]](/images/smileys/cap.gif "[cap]")
|
|
|
| |
|
Hallo und guten Morgen,
ich würd sagen, der Induktionsanfang (n=3) geht auf eine der beiden folgenden Arten: Entweder P ist selber Minkowski-Summe mit
einem Summanden, oder [mm] P=P\oplus\{0\}, [/mm] wenn Du unbedingt mindestens zwei Summanden zum Gründen einer Minkowski-Summe
brauchst.
Der Induktionsschritt schaut vernünftig aus - ich hab nicht alles Wort für Wort gelesen, aber das Prinzip ist richtig.
Gruss,
Mathias
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:48 Di 13.06.2006 | | Autor: | Galois |
Hallo Bastiane, hallo mathiash!
> Und dann auch noch so eine schön erzählte - erinnert mich an
> Pauls Antwort mit dem Buchhalter und eine mit einem Kamin.
> (ich glaub, mit letzterer wollte er mir ein Vektorfeld
> oder so etwas ähnliches erklären. )
Ja, ich habe da manchmal eine gewisse Affinität zu Sikinien. (Falls Dir das Land nichts sagt: -> Google) Die von Dir genannten Beiträge von Paul muß ich mir bei Gelegenheit mal raussuchen. Ich liebe soetwas.
> > Ich gebe Dir mal eine anschauliche Lösung, die Details
> > kannst Du dann ja selbst ausarbeiten.
>
> Das habe ich jetzt mal versucht. Kannst du (oder natürlich
> auch ggf. jemand anders) bitte nochmal drübergucken?
Ist jetzt wahrscheinlich etwas spät, mache ich aber trotzdem. (Ach, was bin ich heute wieder nett...)
> Ich kann das noch nicht ganz so mit dem Abstrahieren (heißt das so?).
Ja, das Wort gibt es. ![[ok]](/images/smileys/ok.gif "[ok]") Ich selbst würde hier eher von "Formalisieren" sprechen, aber die Grenzen sind da wohl fließend.
> Außerdem habe ich fast nur Text - ist das ok, oder kann/muss man das noch mehr in "Formeln" bringen?
Das hängt davon ab, was in Eurer Vorlesung bzw. Übung konkret von euch erwartet wird. Für den Hausgebrauch reicht eine solche Lösung sicherlich, für eine Veröffentlichung würde ich das mindestens für den [mm]R^n[/mm] verallgemeinern und mit ganz vielen Formeln vollstopfen. Soll dann ja nicht nur stimmen, sondern auch nach etwas aussehen.
> Beweis durch Induktion nach n:=Anzahl der Kanten des Polygons
>
> Induktionsanfang:
> n=3
> Lege das Dreieck P in den Ursprung und [mm]s:=\mbox{die kürzeste Kante}[/mm]
> irgendwo hin. Dann gilt: [mm]P=P\oplus s[/mm] [mm]\to[/mm] fertig.
>
> Man braucht doch immer ein "Bezugssystem" oder? Oder kann
> ich einfach schreiben, dass [mm]P=P\oplus s[/mm] ohne zu sagen, dass
> P im Ursprung liegt und s irgendwo? (Außerdem ginge es auch
> anders: s in den Ursprung und P irgendwo, oder?)
Zum Induktionsanfang hat Mathias ja schon etwas geschrieben. Die Identität [mm]P=P\oplus s[/mm] ist hingegen i. allg. nicht richtig, da Du zur Konstruktion von [mm]P\oplus s[/mm] ja das Dreicke P entlang einer seiner Kanten s verschiebst -> die überstrichene Fläche [mm]P\oplus s[/mm] ist ein Viereck (genauer: ein Trapez)!
Zur Frage nach dem Ursprung: Eigentlich wäre es schon genauer, wenn man sagt, wo die einzelnen Summanden genau liegen. Sofern es einem aber nur um das "Aussehen" der Summe [mm]\mathcal A\oplus \mathcal B[/mm] selbst geht, kann man diesen Aspekt jedoch ohne schlechtes Gewissen unter den Tisch fallen lassen: Denn eine Verschiebung z.B. von [mm]\mathcal A[/mm] um einen Vektor v ändert die Summe [mm]\mathcal A\oplus \mathcal B[/mm] nur in sofern, als daß diese dann auch um v verschoben wird.
> Induktionsvoraussetzung:
> Jedes Polygon mit n Ecken ist darstellbar als
> Minkowski-Summe von Dreiecken und Strecken.
>
> Induktionsschritt: [mm]n\to n+1[/mm]
> Sei s die kürzeste Seite des
> Polygons P und P' das Polygon, das aus
> Parallelverschiebungen von s entlang des Randes von P
> ensteht.
> (Ist das klar, was damit gemeint ist? Oder kann man das
> noch anders formulieren? [...])
Für mich ist das klar, aber ich bin befangen. Formal könnte man zum Beispiel [mm]P':=P\cap(P+s)[/mm] (s hierbei als Vektor aufgefaßt, "+" die normale Summe im Vektorraum) schreiben. Ich glaube aber nicht, daß das verständlicher wäre...
> P' besteht offenbar aus n-1 Ecken und somit auch n-1 Kanten.
> (Ist das trivial? Oder muss ich das auch noch irgendwie
> beweisen?)
Das ist nicht nur nicht trivial, sondern sogar falsch. ![[traurig]](/images/smileys/traurig.gif "[traurig]") Mir ist da gestern abend leider ein Fehler unterlaufen:
Falls (beispielsweise) das Polygon oben eine sehr lange und spitze Spitze hat, die durch Ecken mit Innenwinkeln nahe an 180° unterteilt ist, erreicht man mehrere Ecken/Kanten nicht. Entsprechend hätte das Polygon P' dann auch weniger Kanten. Letzteres ist nicht schlimm - ersteres schon.
> Fall 1: Die gegenüberliegende Seite von s ist parallel zu s
> [mm]\to[/mm] [mm]P=P'\oplus s[/mm](wiederum mit s im Ursprung und P'
> irgendwo oder umgekehrt) [mm]\to[/mm] fertig
Wobei es hier übrigens auch vorkommen kann, daß P' nur n-2 Kanten hat. Was aber nicht wirklich stört.
> Fall 2: Die gegenüberliegende Seite von s ist nicht
> parallel zu s
> [mm]\to[/mm] Bei der Parallelverschiebung bleibt eine "Spitze"
> übrig. Diese nennen wir s'. Setzen wir diese Spitze auf die
> Kante s - es einsteht ein Dreieck s'' - und machen noch
> einmal unsere Parallelverschiebung, so entsteht das selbe
> Polygon P' wie vorher, aber es bleibt keine Spitze mehr
> übrig.
> [mm]\to[/mm] [mm]P=P'\oplus s''[/mm](wiederum mit s'' im Ursprung und P'
> irgendwo oder umgekehrt) [mm]\to[/mm] fertig
Wie gesagt, hier besteht das Problem, daß die Spitze s' bzw. s'' nicht notwendigerweise ein Dreieck ist.
Man kann dies folgendermaßen reparieren: Wir verkleinern unsere waagerechte "Staubsaugerdüse" s gerade soweit, bis die zugehörige Restspitze s' tatsächlich ein Dreieck ist. Dann hat P' n-1 oder n-2 Kanten und die restliche Argumentation stimmt weiterhin.
(Übrigens brauchen wir bei Berücksichtigung dieser Modifikation dann auch gar nicht mehr vorauszusetzen, daß s die kürzeste Kante ist.)
> Ach ja, ich sollte vielleicht noch erwähnen, dass für P'
> die Aussagen natürlich nach Induktionsvoraussetzung gilt.
>
>
> Es muss nicht perfekt sein - aber kann man das so aufschreiben???
Dein Tutor wird vermutlich froh darüber sein, mal keinen Formelwust präsentiert zu bekommen. Ich bin aber mal gespannt, ob er den oben angesprochenen Fehler ebenfalls findet.
> > P.S.: Macht ihr das gerade in Praktischer Mathematik?
>
> Nein , in dieser netten Vorlesung. Und die gehört meines Wissens zur theoretischen Informatik.
Ah, "Bewegungsplanung für Roboter". Da lag ich mit meinem Staubsauger doch gar nicht mal so falsch. Ein Staubsauger-Roboter ist schließlich auch was Feines.
Grüße in die Römerstraße,
Galois
![[hut]](/images/smileys/hut.gif "[hut]")
|
|
|
|
