Hyperebenentrennungssatz

Hyperebenentrennungssatz (Umgeleitet von Trennungsachsensatz) Zur Navigation springen Zur Suche springen Hyperebenen-Trennungssatz Illustration des Hyperebenen-Trennungssatzes.

Typ Satz Feld Konvexe Geometrie Topologische Vektorräume Kollisionserkennung Vermutung von Hermann Minkowski Offenes Problem Nein Verallgemeinerungen Trennungssatz von Hahn-Banach In der Geometrie, Der Hyperebenen-Trennsatz ist ein Satz über disjunkte konvexe Mengen im n-dimensionalen euklidischen Raum. Es gibt mehrere ziemlich ähnliche Versionen. In einer Version des Theorems, wenn beide Mengen abgeschlossen sind und mindestens eine davon kompakt ist, dann gibt es eine Hyperebene dazwischen und sogar zwei parallele Hyperebenen dazwischen, die durch eine Lücke getrennt sind. In einer anderen Version, wenn beide disjunkten konvexen Mengen offen sind, dann gibt es eine Hyperebene zwischen ihnen, aber nicht unbedingt eine Lücke. Eine Achse, die orthogonal zu einer trennenden Hyperebene ist, ist eine trennende Achse, weil die orthogonalen Projektionen der konvexen Körper auf die Achse disjunkt sind.

Der Hyperebenen-Trennsatz stammt von Hermann Minkowski. Das Hahn-Banach-Trennungstheorem verallgemeinert das Ergebnis auf topologische Vektorräume.

Ein verwandtes Ergebnis ist der unterstützende Hyperebenensatz.

Im Kontext von Support-Vektor-Maschinen, Die optimal trennende Hyperebene oder Hyperebene mit maximalem Rand ist eine Hyperebene, die zwei konvexe Hüllen von Punkten trennt und von den beiden gleich weit entfernt ist.[1][2][3] Inhalt 1 Aussagen und Beweise 2 Umkehrung des Satzes 3 Gegenbeispiele und Eindeutigkeit 4 Verwendung in der Kollisionserkennung 5 Siehe auch 6 Anmerkungen 7 Verweise 8 External links Statements and proof Hyperplane separation theorem[4] — Let A and B be two disjoint nonempty convex subsets of Rn. Dann gibt es einen von Null verschiedenen Vektor v und eine reelle Zahl c, so dass {Anzeigestil Sprache x,wrangle geq c,{Text{ und }}y-Winkel,vrangle leq c} für alle x in A und y in B; d.h., die Hyperebene {displaystyle langle cdot ,vrangle = c} , v der Normalenvektor, trennt A und B.

Der Beweis basiert auf dem folgenden Lemma: Lemma — Let {Anzeigestil K} eine nichtleere abgeschlossene konvexe Teilmenge von Rn. Dann existiert ein eindeutiger Vektor in {Anzeigestil K} der Mindestnorm (Länge).

Beweis des Lemmas: Lassen {Anzeigestil Delta =inf{|x|:bitte KY}.} Lassen {Anzeigestil x_{j}} sei eine Folge in {Anzeigestil K} so dass {Anzeigestil |x_{j}|zu delta } . Beachten Sie, dass {Anzeigestil (x_{ich}+x_{j})/2} ist in {Anzeigestil K} seit {Anzeigestil K} ist konvex und so {Anzeigestil |x_{ich}+x_{j}|^{2}geq 4delta ^{2}} . Seit {Anzeigestil |x_{ich}-x_{j}|^{2}=2|x_{ich}|^{2}+2|x_{j}|^{2}-|x_{ich}+x_{j}|^{2}leq 2|x_{ich}|^{2}+2|x_{j}|^{2}-4Delta ^{2}zu 0} wie {Anzeigestil i,jto infty } , {Anzeigestil x_{ich}} ist eine Cauchy-Folge und hat daher den Grenzwert x in {Anzeigestil K} . Es ist eindeutig, da wenn y in ist {Anzeigestil K} und hat die Norm δ, dann {Anzeigestil |x-y|^{2}leq 2|x|^{2}+2|j|^{2}-4Delta ^{2}=0} und x = y. {Quadrat im Display-Stil } Beweis des Satzes: Gegeben disjunkte nichtleere konvexe Mengen A, B, Lassen {Anzeigestil K=A+(-B)={x-ymid xin A,Yin B}.} Seit {Anzeigestil -B} konvex ist und die Summe konvexer Mengen konvex ist, {Anzeigestil K} ist konvex. Durch das Lemma, die Schließung {Anzeigestil {überstreichen {K}}} von {Anzeigestil K} , was konvex ist, enthält einen Vektor {Anzeigestil v} der Mindestnorm. Seit {Anzeigestil {überstreichen {K}}} ist konvex, für alle {Anzeigestil n} in {Anzeigestil K} , das Liniensegment {Anzeigestil v+t(n-v),,0leq tleq 1} besteht in {Anzeigestil {überstreichen {K}}} und so {Anzeigestil |v|^{2}leq |v+t(n-v)|^{2}=|v|^{2}+2feiern V,n-vrangle +t^{2}|n-v|^{2}} .

Zum {Anzeigestil 0c_{2},{Text{ und }}y-Winkel,zappelnd c,{Text{ und }}y-Winkel,vrangle leq c} für alle x in A und y in B. Wenn beide Sätze offen sind, dann gibt es einen Vektor v ungleich Null und eine reelle Zahl {Anzeigestil c} so dass {Anzeigestil Sprache x,vrangle >c,{Text{ und }}y-Winkel,zappelnd 0,ygeq 1/x}. } (Obwohl, durch eine Instanz des zweiten Theorems, es gibt eine Hyperebene, die ihre Innenräume trennt.) Eine andere Art von Gegenbeispiel hat A kompakt und B offen. Zum Beispiel, A kann ein geschlossenes Quadrat sein und B kann ein offenes Quadrat sein, das A berührt.

In der ersten Version des Theorems, offensichtlich ist die trennende Hyperebene niemals eindeutig. In der zweiten Fassung, es kann einzigartig sein oder nicht. Technisch gesehen ist eine Trennachse nie eindeutig, weil sie übersetzt werden kann; in der zweiten Version des Theorems, eine Trennachse kann bis auf Translation eindeutig sein.

Use in collision detection The separating axis theorem (SA) sagt, dass: Zwei konvexe Objekte überlappen sich nicht, wenn es eine Linie gibt (Achse genannt) auf die sich die Projektionen der beiden Objekte nicht überschneiden.

SAT schlägt einen Algorithmus zum Testen vor, ob sich zwei konvexe Körper schneiden oder nicht.

Unabhängig von der Dimensionalität, die Trennachse ist immer eine Linie. Zum Beispiel, in 3D, der raum ist durch ebenen getrennt, aber die Trennachse steht senkrecht auf der Trennebene.

Der Trennungsachsensatz kann zur schnellen Kollisionserkennung zwischen Polygonmaschen angewendet werden. Die Normalen- oder andere Merkmalsrichtung jeder Fläche wird als Trennachse verwendet. Beachten Sie, dass dies mögliche Trennachsen ergibt, Linien/Ebenen nicht trennen.

In 3D, Die alleinige Verwendung von Flächennormalen wird einige nicht kollidierende Kante-an-Kante-Fälle nicht trennen können. Zusätzliche Achsen, bestehend aus den Kreuzprodukten von Kantenpaaren, eine von jedem Objekt, sind erforderlich.[6] Für mehr Effizienz, parallele Achsen können als eine einzige Achse berechnet werden.

Siehe auch Doppelkegel Lemma von Farkas Kirchbergers Theorem Optimale Steuerung Anmerkungen ^ Hastie, Trevor; Tibshirani, Robert; Friedmann, Hieronymus (2008). The Elements of Statistical Learning : Data-Mining, Inferenz, und Vorhersage (Pdf) (Zweite Aufl.). New York: Springer. pp. 129–135. ^ Witten, Ian H.; Frank, Eibe; Saal, Markus A.; Kumpel, Christoph J. (2016). Data-Mining: Praktische Tools und Techniken für maschinelles Lernen (Fourth ed.). Morgan Kaufmann. pp. 253–254. ISBN 9780128043578. ^ Deisenroth, Markus Peter; Faisal, EIN. Aldo; Ong, Cheng Bald (2020). Mathematik für maschinelles Lernen. Cambridge University Press. pp. 337–338. ISBN 978-1-108-45514-5. ^ Boyd & Vandenberghe 2004, Übung 2.22. ^ Haim Brezis, Analyse fonctionnelle : Theorie und Anwendungen, 1983, Anmerkung 4, p. 7. ^ "Fortgeschrittene Vektormathematik". Referenzen Boyd, Stefan P.; Vandenberghe, Lieven (2004). Konvexe Optimierung (Pdf). Cambridge University Press. ISBN 978-0-521-83378-3. Golstein, E. G.; Tretjakow, NV. (1996). Modifizierte Lagrange-Operatoren und monotone Karten in der Optimierung. New York: Wiley. p. 6. ISBN 0-471-54821-9. Shimizu, Kiyotaka; Ishizuka, Yo; Barde, Jonatan F. (1997). Nicht differenzierbare und zweistufige mathematische Programmierung. Boston: Kluwer Academic Publishers. p. 19. ISBN 0-7923-9821-1. External links Collision detection and response show vte Functional analysis (Themen – Glossar) show vte Topologische Vektorräume (Fernseher) Kategorien: Sätze der konvexen GeometrieHermann Minkowski