Théorème de séparation hyperplan

Théorème de séparation hyperplan (Redirigé depuis le théorème de l'axe de séparation) Aller à la navigation Aller à la recherche Théorème de séparation d'hyperplan Illustration du théorème de séparation d'hyperplan.

Type Théorème Champ Géométrie convexe Espaces vectoriels topologiques Détection de collision Conjecturé par Hermann Minkowski Problème ouvert Non Généralisations Théorème de séparation Hahn-Banach En géométrie, le théorème de séparation d'hyperplan est un théorème sur les ensembles convexes disjoints dans l'espace euclidien à n dimensions. Il existe plusieurs versions assez similaires. Dans une version du théorème, si ces deux ensembles sont fermés et qu'au moins l'un d'eux est compact, alors il y a un hyperplan entre eux et même deux hyperplans parallèles entre eux séparés par un espace. Dans une autre version, si les deux ensembles convexes disjoints sont ouverts, alors il y a un hyperplan entre eux, mais pas nécessairement d'écart. Un axe orthogonal à un hyperplan séparateur est un axe séparateur, parce que les projections orthogonales des corps convexes sur l'axe sont disjointes.

Le théorème de séparation des hyperplans est dû à Hermann Minkowski. Le théorème de séparation Hahn – Banach généralise le résultat aux espaces vectoriels topologiques.

Un résultat connexe est le théorème d'hyperplan de support.

Dans le cadre des machines à vecteurs supports, l'hyperplan de séparation optimale ou l'hyperplan à marge maximale est un hyperplan qui sépare deux coques convexes de points et est équidistant des deux.[1][2][3] Contenu 1 Déclarations et preuves 2 Inverse du théorème 3 Contre-exemples et unicité 4 Utilisation dans la détection de collision 5 Voir également 6 Remarques 7 Références 8 External links Statements and proof Hyperplane separation theorem[4] — Let A and B be two disjoint nonempty convex subsets of Rn. Alors il existe un vecteur v non nul et un nombre réel c tel que {displaystyle langle x,se disputer geq c,{texte{ et }}langle y,vrangle leq c} pour tout x dans A et y dans B; c'est à dire., l'hyperplan {displaystyle langle cdot ,angle =c} , v le vecteur normal, sépare A et B.

La preuve est basée sur le lemme suivant: Lemma — Let {style d'affichage K} un sous-ensemble convexe fermé non vide de Rn. Alors il existe un vecteur unique dans {style d'affichage K} de la norme minimale (longueur).

Preuve du lemme: Laisser {style d'affichage delta =inf{|X|:s'il vous plaît KY}.} Laisser {style d'affichage x_{j}} être une séquence dans {style d'affichage K} tel que {style d'affichage |X_{j}|au delta } . Notez que {style d'affichage (X_{je}+X_{j})/2} est dans {style d'affichage K} puisque {style d'affichage K} est convexe et donc {style d'affichage |X_{je}+X_{j}|^{2}geq 4delta ^{2}} . Depuis {style d'affichage |X_{je}-X_{j}|^{2}=2|X_{je}|^{2}+2|X_{j}|^{2}-|X_{je}+X_{j}|^{2}leq 2|X_{je}|^{2}+2|X_{j}|^{2}-4delta ^{2}à 0} comme {style d'affichage i,jto infty } , {style d'affichage x_{je}} est une suite de Cauchy et a donc pour limite x dans {style d'affichage K} . Il est unique puisque si y est dans {style d'affichage K} et de norme δ, alors {style d'affichage |x-y|^{2}leq 2|X|^{2}+2|y|^{2}-4delta ^{2}=0} et x = y. {carré de style d'affichage } Preuve du théorème: Étant donné des ensembles convexes non vides disjoints A, B, laisser {style d'affichage K=A+(-B)={x-ymid xin A,yin B}.} Depuis {style d'affichage -B} est convexe et la somme des ensembles convexes est convexe, {style d'affichage K} est convexe. Par le lemme, la fermeture {style d'affichage {surligner {K}}} de {style d'affichage K} , qui est convexe, contient un vecteur {style d'affichage v} de la norme minimale. Depuis {style d'affichage {surligner {K}}} est convexe, pour toute {displaystyle n} dans {style d'affichage K} , le segment de ligne {style d'affichage v+t(n-v),,0leq tleq 1} réside dans {style d'affichage {surligner {K}}} et donc {style d'affichage |v|^{2}leq |v+t(n-v)|^{2}=|v|^{2}+2célébrer v,n-angle +t^{2}|n-v|^{2}} .

Pour {style d'affichage 0c_{2},{texte{ et }}langle y,frétillement c,{texte{ et }}langle y,vrangle leq c} pour tout x dans A et y dans B. Si les deux ensembles sont ouverts, alors il existe un vecteur v non nul et un nombre réel {displaystyle c} tel que {displaystyle langle x,vrangle >c,{texte{ et }}langle y,frétillement 0,ygeq 1/x}. } (Bien que, par une instance du second théorème, il y a un hyperplan qui sépare leurs intérieurs.) Un autre type de contre-exemple a A compact et B ouvert. Par exemple, A peut être un carré fermé et B peut être un carré ouvert qui touche A.

Dans la première version du théorème, évidemment l'hyperplan séparateur n'est jamais unique. Dans la deuxième version, il peut être unique ou non. Techniquement, un axe de séparation n'est jamais unique car il peut être translaté; dans la deuxième version du théorème, un axe de séparation peut être unique jusqu'à la translation.

Use in collision detection The separating axis theorem (ASSIS) dit ça: Deux objets convexes ne se chevauchent pas s'il existe une ligne (appelé axe) sur lequel les projections des deux objets ne se chevauchent pas.

SAT propose un algorithme pour tester si deux solides convexes se croisent ou non.

Indépendamment de la dimensionnalité, l'axe de séparation est toujours une ligne. Par exemple, en 3D, l'espace est séparé par des plans, mais l'axe de séparation est perpendiculaire au plan de séparation.

Le théorème de l'axe de séparation peut être appliqué pour une détection rapide des collisions entre les maillages polygonaux. La direction normale ou autre de chaque face est utilisée comme axe de séparation. Notez que cela donne des axes de séparation possibles, ne pas séparer les lignes/plans.

En 3D, l'utilisation des normales de face seules ne permettra pas de séparer certains cas sans collision bord à bord. Axes supplémentaires, constitué des produits croisés de paires d'arêtes, un extrait de chaque objet, sont requises.[6] Pour une efficacité accrue, les axes parallèles peuvent être calculés comme un seul axe.

Voir aussi Double cône Lemme de Farkas Théorème de Kirchberger Contrôle optimal Notes ^ Hastie, Trévor; Tibshirani, robert; Friedmann, Jérôme (2008). The Elements of Statistical Learning : Exploration de données, Inférence, et prédiction (PDF) (Deuxième éd.). New York: Springer. pp. 129–135. ^ écrit, Ian H.; Franc, if; Salle, Marc A; Copain, Christophe J.. (2016). Exploration de données: Outils et techniques pratiques d'apprentissage automatique (Fourth ed.). Morgan Kaufmann. pp. 253–254. ISBN 9780128043578. ^ Deisenroth, Marc Pierre; Fayçal, UN. Aldo; Ong, Cheng Bientôt (2020). Mathématiques pour l'apprentissage automatique. la presse de l'Universite de Cambridge. pp. 337–338. ISBN 978-1-108-45514-5. ^ Boyd & Vandenberghe 2004, Exercer 2.22. ^ Haïm Brezis, Analyse fonctionnelle : théorie et applications, 1983, remarque 4, p. 7. ^ "Mathématiques vectorielles avancées". Références Boyd, Stéphane P.; Vandenberghe, Lieven (2004). Optimisation convexe (PDF). la presse de l'Universite de Cambridge. ISBN 978-0-521-83378-3. Golstein, E. G.; Tretiakov, NV. (1996). Lagrangiens modifiés et cartes monotones en optimisation. New York: Wiley. p. 6. ISBN 0-471-54821-9. Shimizu, Kiyotaka; Ishizuka, Yo; Barde, Jonathan F.. (1997). Programmation mathématique non différentiable et à deux niveaux. Boston: Éditeurs académiques Kluwer. p. 19. ISBN 0-7923-9821-1. External links Collision detection and response show vte Functional analysis (sujets – glossaire) show vte Espaces vectoriels topologiques (téléviseurs) Catégories: Théorèmes en géométrie convexeHermann Minkowski