MastersForum

Quoted

wobei ich glaube, dass es immer Eingaben gibt, wo die Laufzeit quadratisch in r wird (lasse mich da aber gern eines Besseren belehren).

Quoted

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.

Quoted

Original von plexiq
Für:
(0,2,0,1)
(1,2,0,1)

Ergeben sich ebenfalls genau 2 Flächen?
1: (0,0),(1,0),(1,1),(0,1),(0,0)
2: (1,0),(2,0),(2,1),(1,1), (1,0)

Quoted

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).

Quoted

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.

Quoted

Original von plizzz
Ich habe doch nicht geschrieben, dass die Polygonzüge disjunkt sind. Ich habe geschrieben, dass die Polygone disjunkt sind.

Quoted

Original von plizzz
Aber gut: Ich habe eine Menge von Rechtecken im R^2 gegeben. Jedes Rechteck spaltet den R^2 in zwei Teile.

Quoted

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.

Quoted

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.

Quoted

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...)

Quoted

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.

Quoted

Original von plizzz

Quoted

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.

Quoted

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.