Teorema di separazione dell'iperpiano

Teorema di separazione dell'iperpiano (Reindirizzato da Teorema dell'asse di separazione) Vai alla navigazione Vai alla ricerca Teorema di separazione dell'iperpiano Illustrazione del teorema di separazione dell'iperpiano.

Tipo Teorema Campo Geometria convessa Spazi vettoriali topologici Rilevamento di collisioni Congetturato da Hermann Minkowski Problema aperto Nessuna generalizzazione Teorema di separazione di Hahn–Banach In geometria, il teorema di separazione dell'iperpiano è un teorema sugli insiemi convessi disgiunti nello spazio euclideo n-dimensionale. Ci sono diverse versioni piuttosto simili. In una versione del teorema, se entrambi questi insiemi sono chiusi e almeno uno di essi è compatto, poi c'è un iperpiano tra di loro e anche due iperpiani paralleli tra di loro separati da uno spazio vuoto. In un'altra versione, se entrambi gli insiemi convessi disgiunti sono aperti, poi c'è un iperpiano tra di loro, ma non necessariamente un divario. Un asse che è ortogonale a un iperpiano di separazione è un asse di separazione, perché le proiezioni ortogonali dei corpi convessi sull'asse sono disgiunte.

Il teorema di separazione dell'iperpiano è dovuto a Hermann Minkowski. Il teorema di separazione di Hahn-Banach generalizza il risultato a spazi vettoriali topologici.

Un risultato correlato è il teorema dell'iperpiano di supporto.

Nel contesto delle macchine vettore di supporto, l'iperpiano che separa in modo ottimale o l'iperpiano del margine massimo è un iperpiano che separa due scafi di punti convessi ed è equidistante dai due.[1][2][3] Contenuti 1 Dichiarazioni e prove 2 Converse del teorema 3 Controesempi e unicità 4 Utilizzare nel rilevamento delle collisioni 5 Guarda anche 6 Appunti 7 Riferimenti 8 External links Statements and proof Hyperplane separation theorem[4] — Let A and B be two disjoint nonempty convex subsets of Rn. Allora esistono un vettore v diverso da zero e un numero reale c tale che {angolo dello stile di visualizzazione x,litigare geq c,{testo{ e }}angolo y,vrangle leq c} per ogni x in A e y in B; cioè., l'iperpiano {displaystyle angolo cdot ,vrangle = c} , v il vettore normale, separa A e B.

La dimostrazione si basa sul seguente lemma: Lemma — Let {stile di visualizzazione K} essere un sottoinsieme convesso chiuso non vuoto di Rn. Allora esiste un vettore univoco in {stile di visualizzazione K} di norma minima (lunghezza).

Prova del lemma: Permettere {displaystyle delta = inf{|X|:per favore KY}.} Permettere {stile di visualizzazione x_{j}} essere una sequenza in {stile di visualizzazione K} tale che {stile di visualizzazione |X_{j}|a delta } . Notare che {stile di visualizzazione (X_{io}+X_{j})/2} è dentro {stile di visualizzazione K} da {stile di visualizzazione K} è convesso e così {stile di visualizzazione |X_{io}+X_{j}|^{2}geq 4delta ^{2}} . Da {stile di visualizzazione |X_{io}-X_{j}|^{2}=2|X_{io}|^{2}+2|X_{j}|^{2}-|X_{io}+X_{j}|^{2}leq 2|X_{io}|^{2}+2|X_{j}|^{2}-4delta ^{2}a 0} come {stile di visualizzazione i,jto infty } , {stile di visualizzazione x_{io}} è una sequenza di Cauchy e quindi ha limite x in {stile di visualizzazione K} . È unico poiché se y è in {stile di visualizzazione K} e ha norma δ, poi {stile di visualizzazione |x-y|^{2}leq 2|X|^{2}+2|y|^{2}-4delta ^{2}=0} e x = y. {displaystyle quadrato } Dimostrazione del teorema: Dati insiemi convessi disgiunti non vuoti A, B, permettere {stile di visualizzazione K=A+(-B)={x-ymid xin A,yin B}.} Da {stile di visualizzazione -B} è convesso e la somma degli insiemi convessi è convessa, {stile di visualizzazione K} è convesso. Per il lemma, la chiusura {stile di visualizzazione {sopra {K}}} di {stile di visualizzazione K} , che è convesso, contiene un vettore {stile di visualizzazione v} di norma minima. Da {stile di visualizzazione {sopra {K}}} è convesso, per ogni {stile di visualizzazione n} in {stile di visualizzazione K} , il segmento di linea {stile di visualizzazione v+t(n-v),,0leq tleq 1} si trova in {stile di visualizzazione {sopra {K}}} e così {stile di visualizzazione |v|^{2}leq |v+t(n-v)|^{2}=|v|^{2}+2celebrare v,n-vrangle +t^{2}|n-v|^{2}} .

Per {stile di visualizzazione 0c_{2},{testo{ e }}angolo y,dimenando c,{testo{ e }}angolo y,vrangle leq c} per ogni x in A e y in B. Se entrambi i set sono aperti, allora esistono un vettore v diverso da zero e un numero reale {stile di visualizzazione c} tale che {angolo dello stile di visualizzazione x,vrangle >c,{testo{ e }}angolo y,dimenando 0,ygeq 1/x}. } (Sebbene, da un'istanza del secondo teorema, c'è un iperpiano che separa i loro interni.) Un altro tipo di controesempio ha A compatto e B aperto. Per esempio, A può essere un quadrato chiuso e B può essere un quadrato aperto che tocca A.

Nella prima versione del teorema, evidentemente l'iperpiano di separazione non è mai unico. Nella seconda versione, può o non può essere unico. Tecnicamente un asse separatore non è mai univoco perché traslabile; nella seconda versione del teorema, un asse separatore può essere univoco fino alla traslazione.

Use in collision detection The separating axis theorem (SAB) Dillo: Due oggetti convessi non si sovrappongono se esiste una linea (chiamato asse) su cui le proiezioni dei due oggetti non si sovrappongono.

SAT suggerisce un algoritmo per verificare se due solidi convessi si intersecano o meno.

Indipendentemente dalla dimensionalità, l'asse di separazione è sempre una linea. Per esempio, in 3D, lo spazio è separato da piani, ma l'asse di separazione è perpendicolare al piano di separazione.

Il teorema dell'asse di separazione può essere applicato per il rilevamento rapido delle collisioni tra mesh poligonali. La direzione normale o altra caratteristica di ciascuna faccia viene utilizzata come asse di separazione. Si noti che questo produce possibili assi di separazione, non separano linee/piani.

In 3D, l'uso delle normali facciali da solo non riuscirà a separare alcuni casi bordo su bordo non in conflitto. Assi aggiuntivi, costituito dai prodotti incrociati di coppie di spigoli, uno preso da ogni oggetto, sono richiesti.[6] Per una maggiore efficienza, assi paralleli possono essere calcolati come un singolo asse.

Vedi anche Dual cone Lemma di Farkas Teorema di Kirchberger Controllo ottimale Note ^ Hastie, Trevor; Tibshirani, Roberto; Friedman, Girolamo (2008). The Elements of Statistical Learning : Estrazione dei dati, Inferenza, e previsione (PDF) (Seconda ed.). New York: Springer. pp. 129–135. ^ Witten, Ian H.; Franco, tasso; Sala, Marco A.; Amico, Christopher J. (2016). Estrazione dei dati: Strumenti pratici e tecniche di apprendimento automatico (Fourth ed.). Morgan Kaufman. pp. 253–254. ISBN 9780128043578. ^ Deisenroth, Marco Pietro; Faisal, UN. Aldo; Ong, Cheng presto (2020). Matematica per l'apprendimento automatico. Cambridge University Press. pp. 337–338. ISBN 978-1-108-45514-5. ^ Boyd & Vandenberghe 2004, Esercizio 2.22. ^ Haim Brezis, Analyse fonctionnelle : teoria e applicazioni, 1983, osservazione 4, p. 7. ^ "Matematica vettoriale avanzata". Riferimenti Boyd, Stefano P.; Vandenberghe, Lieven (2004). Ottimizzazione convessa (PDF). Cambridge University Press. ISBN 978-0-521-83378-3. Golstein, e. G.; Tret'jakov, N.V. (1996). Modificate lagrangiane e mappe monotone in ottimizzazione. New York: Wiley. p. 6. ISBN 0-471-54821-9. Shimizu, Kiyotaka; Ishizuka, Yo; Bardo, Jonathan F. (1997). Programmazione matematica indifferenziabile ea due livelli. Boston: Editori accademici Kluwer. p. 19. ISBN 0-7923-9821-1. External links Collision detection and response show vte Functional analysis (argomenti – glossario) mostra vte Spazi vettoriali topologici (TV) Categorie: Teoremi in geometria convessa Hermann Minkowski