Definition konvexer Mengen durch Polytope

29/04/2009 - 09:52 von quarterpounder | Report spam
Hallo Zusammen,

ich möchte in höherdimensional (4 bis 6) Ràumen mittels Polytopen
konvexe Mengen definieren. Das heisst, ich habe eine Ausgangsmenge,
und verkleinere ein Polytop "konvex" derart, bis nur noch Elemente
der Ausgangsmenge enthalten sind. Die Algorithmen hierzu sind klar.

Nicht so einfach ist dann aber der umgekehrte Weg, zu dem ich denn die
Frage habe. Wenn das Polytop definiert ist, festuzustellen, ob ein
fraglicher Punkt innerhalb dieses Polytops liegt. Es gibt offenbar ine
Vielzahl von Algorithmen, die mir eine Aussege darüber liefern, z.B.
Fourier-Motzkin. Allerdings sind diese teilweise sehr kompliziert,
schlecht anzuwenden oder benötigen aufwàdige Datenstrukturen oder
haben lange Laufzeiten.

Ich suche nun nach Sonder-Polytopen, vielleicht mit besonderen
Symmetrieeigenschaften, damit ich diese Aufgabe einfach lösen kann.
Im dreidimensionalen Raum scheint es für platonische Körper recht
einfach zu sein, diesen Member-Test durchzuführen. Denn es kann
einfach die Flàche des Polytops festgestellt werden kann, die
alleine zu prüfen ist, denn die Eckpunkte dieser Flàchen sind
einfachst zu finden. Dass dies so gut funktioniert, liegt eben an den
Symmetrieeigenschaften der platonischen Körper.

Gibt es so etwas auch in höherdimensionalen Ràumen?

Gruß
Erich
 

Lesen sie die antworten

#1 Detlef Müller
30/04/2009 - 09:02 | Warnen spam
quarterpounder schrieb:
Hallo Zusammen,

ich möchte in höherdimensional (4 bis 6) Ràumen mittels Polytopen
konvexe Mengen definieren. Das heisst, ich habe eine Ausgangsmenge,
und verkleinere ein Polytop "konvex" derart, bis nur noch Elemente
der Ausgangsmenge enthalten sind. Die Algorithmen hierzu sind klar.

Nicht so einfach ist dann aber der umgekehrte Weg, zu dem ich denn die
Frage habe. Wenn das Polytop definiert ist, festuzustellen, ob ein
fraglicher Punkt innerhalb dieses Polytops liegt. Es gibt offenbar ine
Vielzahl von Algorithmen, die mir eine Aussege darüber liefern, z.B.
Fourier-Motzkin. Allerdings sind diese teilweise sehr kompliziert,
schlecht anzuwenden oder benötigen aufwàdige Datenstrukturen oder
haben lange Laufzeiten.



Mh, war es nicht so, daß man für jede Hyperebene genau ein
Skalarprodukt ausrechnen muß, um festzustellen ob ein Punkt x auf
der Richtigen Seite liegt?
Da die Menge konvex ist, braucht man maximal für jede Polytopseite ein
Skalarprodukt mit dem Normalenvektor n.

Vermutlich übersehe ich da etwas, das kommt mir nàmlich nicht wirklich
aufwàndig oder kompliziert vor, als Datenstruktur muß man nur
eine Liste der Normalenvektoren der Begrenzungsebenen haben
(oder ist der Haken - wie so oft - bei dem Schlüsselwort "nur"?).

Gruß,
Detlef
Dr. Detlef Müller,
http://www.mathe-doktor.de oder http://mathe-doktor.de

Ähnliche fragen