Sie sind nicht angemeldet.
28.05.2010, 12:29
Zitat
wobei ich glaube, dass es immer Eingaben gibt, wo die Laufzeit quadratisch in r wird (lasse mich da aber gern eines Besseren belehren).
28.05.2010, 12:59
28.05.2010, 13:18
Nun überschneiden sich diese Rechtecke beliebig und ich möchte daraus eben disjunkte Polygonflächen machen, d.h. die Eingabe in eine Reihe von Polygonzügen umwandeln, sodass die Polygonflächen daraus eben paarweise disjunkt sind.
Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »plexiq« (28.05.2010, 13:28)
28.05.2010, 14:37
Es lassen sich einfach Eingaben konstruieren bei denen die Anzahl der Polygone quadratisch mit r wächst, dh besser als O(r^2) gehts definitiv nicht.
Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »plizzz« (28.05.2010, 14:47)
28.05.2010, 14:42
Original von plizzz
Ok, da habe ich etwas geschlampt. In der Tat muss nur das Innere der Rechtecke disjunkt sein, außerdem gibt es keine 1-dimensionsalen Rechtecke (d.h. Liniensegmente).
Original von plizzz
Das ist ein Teil eines Programmierprojektes (als Veranstaltung an der Uni), bei dem es darum geht, zu einer gegebenen Menge polygonaler Hindernisse, die hier durch die nicht disjunkten Rechtecke dargestellt wird, kürzeste Wege zwischen Punkten zu finden, wobei diese Wege die Hindernisse nicht schneiden dürfen. Sie dürfen aber auf dem Rand eines Hindernisses entlanglaufen.
Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von »AtroX_Worf« (28.05.2010, 14:45)
28.05.2010, 15:05
Original von plizzz
Ich habe doch nicht geschrieben, dass die Polygonzüge disjunkt sind. Ich habe geschrieben, dass die Polygone disjunkt sind.
Original von plizzz
Aber gut: Ich habe eine Menge von Rechtecken im R^2 gegeben. Jedes Rechteck spaltet den R^2 in zwei Teile.
Original von plizzz
Nun nehme ich den inneren Teil jedes Rechtecks (ohne Rand), also den Teil, der (-infty,infty) nicht enthält. Diese Menge vereinige ich und erhalte eine Punktmenge M in R^2. Allerdings sind die Rechtecke so gegeben, dass die Inneren Flächen der Rechtecke nicht notwendigerweise disjunkt sind.
Original von plizzz
Ich suche nun eine Menge von Polygonzügen, die folgendes erfüllt: Jeder Polygonzug spaltet den R^2 wieder in zwei Teile. Nehme ich von jedem Polygonzug das Innere, so sind diese Flächen (Punktmengen im R^2) paarweise disjunkt. Die Vereinigung dieser Mengen ergibt M.
Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »AtroX_Worf« (28.05.2010, 15:07)
28.05.2010, 15:58
Original von plexiq
Bin oben davon ausgegangen dass 2 Flächen disjunkt sind gdw die "gemeinsame" Fläche 0 ist? (Sorry falls das eine falsche Definition ist...)
28.05.2010, 16:16
Original von plizzz
Die Aufgabenstellung, wie ich sie geschrieben habe, ist an manchen Stellen wirklich mathematisch nicht 100%ig korrekt. Dennoch kann man sie denke ich verstehen, wenn man sich einen Millimeter aus dem Käfig der Definitionen herauswagt und etwas selbst nachdenkt, anstatt die kursiv gedruckten Sätze aus 1000-seitigen Mathebüchern abzuspulen.
28.05.2010, 16:17
Original von plizzz
Es lassen sich einfach Eingaben konstruieren bei denen die Anzahl der Polygone quadratisch mit r wächst, dh besser als O(r^2) gehts definitiv nicht.
Das verstehe ich nicht. Die Anzahl der Polygone kann doch nicht größer werden als die Anzahl der Rechtecke. Ich dachte eher, dass es nicht geht, weil sich immer Instanzen mit O(r^2) vielen Rechteckschnittpunkten konstruieren lassen, die man dann braucht, um die Polygone zu bestimmen.
Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von »plexiq« (28.05.2010, 16:25)
28.05.2010, 16:40
Original von plizzz
Ich dachte eher, dass es nicht geht, weil sich immer Instanzen mit O(r^2) vielen Rechteckschnittpunkten konstruieren lassen, die man dann braucht, um die Polygone zu bestimmen.
28.05.2010, 16:53
Original von plexiq
Ok, denk ich versteh nun wie die aufgabe gemeint ist. (Siehe edit ^)
Original von plizzz
Ich dachte eher, dass es nicht geht, weil sich immer Instanzen mit O(r^2) vielen Rechteckschnittpunkten konstruieren lassen, die man dann braucht, um die Polygone zu bestimmen.
Musst du wirklich alle Schnittpunkte berechnen um die Polygone zu bestimmen? Rein intuitiv würd ich nein sagen.
