Ich denke, wenn man ihn kräftig genug tritt, ist er schon zerlegbar ...
Oder handelt es sich bei Polygon Minkowski nicht um einen polnischen Fußball-Nationalspieler? ;D
*SCNR*
Sorry dafür, ich habe keine Ahnung wovon du redest!:)
Selur
Habe nur das gefunden...
http://web.informatik.uni-bonn.de/I/GeomLab/MinkowskiSum/
(etwa bei der Mitte der Seite)
Ein Applet zur Berechnung der Minkowski-Summe
Durch Klicken mit der linken Maustaste können die Eckpunkte der Polygone eingegeben werden. Die Minkowski-Summe wird berechnet, sobald der Polygoneditor zwei einfache, geschlossene Polygone enthält. Sie wird in beige dargestellt. Es ist auch möglich die Polygone im Nachhinein noch zu verändern, indem man mit der mit der Maus an den Eckpunkten oder an den Kanten zieht, während man die linke Maustaste gedrückt hält.
Wie Minkowskisummen funktionieren und wie das Applet aussieht weiß ich schon. 
Cu Selur
Ich finde eine ganze Menge PDF-Dateien, wenn ich nach "Polygon Minkowski proof" bzw. "... Beweis" suche; das Auswerten muss ich dir allerdings überlassen...
Hmm, also ich bin jetzt nicht so sattelfest, was die Begriffe angeht (was man halt bei einer Schnellbleiche a la Wikipedia so mitnimmt), aber spontan fällt mir als triviale Zerlegung das Polynom selber und der Nullpunkt ein. Oder ein verschobenes Polynom und ein nicht-Nullpunkt.
Zumindest ein Dreieck sollte nicht anders zerlegt werden können. Was meinst du genau mit einfachen Polygonen?
Kopernikus:
zur Klärung:
1. einfaches Polygon = Polygon ohne Löcher und selbstschnitte 
2. Es geht mir nicht um eine einfache Zerlegung des Polygons in Teilpolygone. (siehe: **) Das kann ich beweisen, ist einfach zu zeigen, dass man jedes einfache Polygon triangulieren kann.
---------
LigH: The Minkowski Problem for Polygons ist interessant, geht aber so wie ich das momentan sehe in die flasche Richtung (nicht 100%ig sicher ;)). In http://www.ioi2004.org/documents/tasks/polygon.pdf wird gemacht worüber ich Nachdenke, die Frage ist:
Kann ich immer zwei Polygone B und C finden, so dass ihre Minkowskisumme ein gegebenes C darstellt? (**)
Wenn "Ja", kann ich durch Rekursion der Methode zu jedem Polygon eine Minkowskisumme aufstellen die nur Gerade und Dreiecke enthält.
Falls "Nein", sollte es ein Polygon geben für das sich beweisen kann, dass es nicht zerlegbar ist.
Cu Selur
Weißt du die Antwort und suchst nur den Beweis oder rätselst du noch?
Ich bin auf jeden Fall auf den Beweis gespannt.
Die Antwort ist: Ja, es geht. (zumindest glaube ich das :D)
Ich suche den Beweis (oder die Widerlegung).
- meine Ansatzskizze war quark -
Man sucht quasi ein Argument warum/wie man die Vereinigung von zwei Minkowskisummen wieder als Minkowskisumme darstellen kann.
Cu Selur
Ps.: Mein Problem ist nur, dass ich zu lange drüber nachgedacht habe und mich mit meinen Schlußfolgerungen im Kreis drehe bzw. über das Thema nicht mehr klar denken kann.
Ich bin auf jeden Fall auf den Beweis gespannt.
Bin mir recht sicher, dass das nicht wild ist, man nur den richtigen Denkansatz braucht und ich mir man ende gegen den Kopf schlage udn sagen: "DOH, da hätteste auch draufkommen können." 
Zitat von SelurThe Minkowski Problem for Polygons ist interessant...
Äähh.., also.., Selurchen.., das mit den Polygonen krieg ich ja (verständnismäßig) noch auf die Reihe.., aber.., wer (zum Teufel) ist MINKOWSKI..? Also.., bei MIR hat der Knabe sich noch nicht vorgestellt..! Hab ich damit jetzt was verpasst.., oder ist das (für mich) wichtig, den Kameraden zu kennen..., und vor allem sein Problem..? :hm:
Gruß, Rudi
Ne, keine Bange Rudi, Minkowski mußte nicht kennen.
Ich beschäftige mich im Studium öfters mal mit Algorithmischer Geometrie und Bewegungsplanungen (z.B. von Roboter) und da sind solche Sachen intressant.
Ist wie ein Knobelspiel nur mit Mathematischen Formeln.
Cu Selur
Tach Rudi,
Zitat von Rudi Ratlos.. wer (zum Teufel) ist MINKOWSKI..?
Zumindest da kann ich auf die Schnelle helfen:
http://de.wikipedia.org/wiki/Hermann_Minkowski
Also in Mathe hat der ein paar tolle Sachen gemacht. Das erste Mal, wo ich mit dem, Namen zu tun hatte, war in L^p-Räumen
Leider kann ich Dir auch grad nicht helfen Selur, weil ich ziemlich mit meinem Vortrag zu kämpfen habe, sonst würde ich mir das gerne anschauen...
Wie ist denn die Minkowski Summe für Polygone definiert? In Wikipedia steht nur eine Definition für Mengen von Punkten. Polygone sind ja aber Tupel, da kommt es ja auf die Reihenfolge an.
Was ich oben meinte, war, dass die Minkowski Summe aus Polygon selber und dem Nullpunkt wieder das Polygon selber ist, bzw. wenn der Punkt von Null verschieden ist, handelt es sich um eine Verschiebung. Aber da wohl einzelne Punkte nicht als Polygone gelten, ist das ja irrelevant.
Zumindest Dreiecke kann man m.E. nicht als Minkowski Summe zweier anderer Polynome darstellen. Das sollte man auch recht einfach zeigen können.
umindest Dreiecke kann man m.E. nicht als Minkowski Summe zweier anderer Polynome darstellen.
Polygone.
Linien und Dreiecke sind quasi die Basis einer Minkowski Summe. D.h. man wird im Endeffekt zeigen, dass ein beliebiges Polygon als Minkowskisumme über Dreicke und Liniensegmenge darstellbar ist. (wobei ich vermute, dass die Kombination auch nicht eindeutig ist)
Wie ist denn die Minkowski Summe für Polygone definiert? In Wikipedia steht nur eine Definition für Mengen von Punkten. Polygone sind ja aber Tupel, da kommt es ja auf die Reihenfolge an.
Polygone werden auch nur als Ansammlung von Punkten gesehen. Genauer bildet man die Summen der Eckpunkte und verbindet sinnig (es gehen ja keine Ecken/Seiten verloren).
Im Applet auf der Bonner Uni Seite (http://web.informatik.uni-bonn.de/I/GeomLab/MinkowskiSum/)
kann man das eigentlich recht gut sehen.
Cu Selur
Zitat von SelurPolygone.
Linien und Dreiecke sind quasi die Basis einer Minkowski Summe. D.h. man wird im Endeffekt zeigen, dass ein beliebiges Polygon als Minkowskisumme über Dreicke und Liniensegmenge darstellbar ist. (wobei ich vermute, dass die Kombination auch nicht eindeutig ist)
Warum ist ein Dreieck kein Polygon? Braucht ein Polygon mehr als 3 Ecken?
Zum Beispiel hab ich schon Zweifel, dass man ein einfaches Rechteck als Minkowski-Summe zweier Dreiecke schreiben kann. Mit zwei Rechtecken wär es möglich, aber da hat man ja nachher nichts gewonnen.
Polygone werden auch nur als Ansammlung von Punkten gesehen. Genauer bildet man die Summen der Eckpunkte und verbindet sinnig (es gehen ja keine Ecken/Seiten verloren).
Dann lässt du aber einen ganzen Haufen Punkte unter den Tisch fallen, die im inneren des Polygons liegen, die laut der Definition auf der uni-bonn Seite dabei wären.
Welche Punkte wählt man denn jetzt letztendlich aus? Intuitiv ist mir das ja klar, aber ich hätte irgendwie gern noch eine etwas formalere Vorschrift, wenn etwas bewiesen werden soll. Konvexe Hülle ist es ja wohl eher nicht, sonst wäre die Einbuchtung auf der Animation nicht mehr dabei.
Warum ist ein Dreieck kein Polygon? Braucht ein Polygon mehr als 3 Ecken?
Mißverständnis. Ein Dreieck ist ein Polygon und eine Linie auch, nur kann man Dreiecke und Linien nicht mehr verkleinern.
Zum Beispiel hab ich schon Zweifel, dass man ein einfaches Rechteck als Minkowski-Summe zweier Dreiecke schreiben kann.
Stimmt das geht nicht, da ja alle Ecken/Geraden erhalten bleiben.
Die Minkowskizerlegung eines Rechtecks wären zwei Geraden.
Dann lässt du aber einen ganzen Haufen Punkte unter den Tisch fallen, die im inneren des Polygons liegen, die laut der Definition auf der uni-bonn Seite dabei wären.
Du addierst (vektromäßig) zu jedem Punkt der Teil des einen Polygons ist jeden Punkt des anderen Polygons. Ja, ein Polygon besteht aus unendlich vielen Punkten, deshalb macht man das in der Praxis nur mit den Eckpunkten, verbindet diese und weiß alles was innen liegt ist Teil der Summe.
Ich hätte irgendwie gern noch eine etwas formalere Vorschrift,
Die einzige Vorschrift die mir geläifig ist, ist die Vorschrift über die die Minkowskisumme allgemein Definiert ist, wie sie auch auf der Seite steht.
Wenn ich einen Stapel Formeln hätte aus denen das mit Umformen zu folgern wäre, wäre ich vermutlich auch schon selber drauf gekommen.
Konvexe Hülle ist es ja wohl eher nicht, sonst wäre die Einbuchtung auf der Animation nicht mehr dabei.
Genau
----
Ich vermute man braucht eventuell noch um das zu beweisen, dass man irgendwas wie eine Minkowski Subraktion einführt, in der Art, dass man ein Polygon als negativ betrachtet, wenn man es spiegel.
Cu Selur
Ps.: vielleicht hilfreich zum Verständnis: http://ad.informatik.uni-freiburg.de/bibliothek/boo…7/slides/08.pdf
-----
Montag: mir ist biem Schlafen eventuell eine Idee gekommen wie ich Beweisen kann, dass es nicht geht. Werd ich heue in der Uni mal genauer drüber nachdenken und falls es passt heute abend posten.
konvexe Polygone Zerlegen geht wie bei http://cgi.di.uoa.gr/~et/papers/et-…n-aggm-2005.pdf gezeigt, konkarve zu zerlegen ist NP-hart und geht nicht immer (z.B. spitze Gabel).
Sie haben noch kein Benutzerkonto auf unserer Seite? Registrieren Sie sich kostenlos und nehmen Sie an unserer Community teil!
