Teorema da separação do hiperplano

Teorema da separação do hiperplano (Redirecionado de Teorema do eixo de separação) Ir para a navegação Ir para a pesquisa Teorema da separação do hiperplano Ilustração do teorema da separação do hiperplano.

Teorema do tipo Campo Geometria convexa Espaços vetoriais topológicos Detecção de colisões Conjecturado por Hermann Minkowski Problema aberto Não Generalizações Teorema da separação de Hahn–Banach Em geometria, o teorema da separação do hiperplano é um teorema sobre conjuntos convexos disjuntos no espaço euclidiano n-dimensional. Existem várias versões bastante semelhantes. Em uma versão do teorema, se ambos os conjuntos são fechados e pelo menos um deles é compacto, então há um hiperplano entre eles e até dois hiperplanos paralelos entre eles separados por uma lacuna. Em outra versão, se ambos os conjuntos convexos disjuntos estiverem abertos, então há um hiperplano entre eles, mas não necessariamente qualquer lacuna. Um eixo que é ortogonal a um hiperplano de separação é um eixo de separação, porque as projeções ortogonais dos corpos convexos sobre o eixo são disjuntas.

O teorema da separação do hiperplano é devido a Hermann Minkowski. O teorema da separação de Hahn–Banach generaliza o resultado para espaços vetoriais topológicos.

Um resultado relacionado é o teorema do hiperplano de suporte.

No contexto de máquinas de vetor de suporte, o hiperplano de separação ideal ou hiperplano de margem máxima é um hiperplano que separa dois cascos convexos de pontos e é equidistante dos dois.[1][2][3] Conteúdo 1 Declarações e provas 2 Reverso do teorema 3 Contra-exemplos e singularidade 4 Use na detecção de colisão 5 Veja também 6 Notas 7 Referências 8 External links Statements and proof Hyperplane separation theorem[4] — Let A and B be two disjoint nonempty convex subsets of Rn. Então existe um vetor diferente de zero v e um número real c tal que {estilo de exibição lang x,disputa geq c,{texto{ e }}ângulo y,vrangle leq c} para todo x em A e y em B; ou seja, o hiperplano {cdot do estilo de exibição ,vrangle = c} , v o vetor normal, separa A e B.

A prova é baseada no seguinte lema: Lemma — Let {estilo de exibição K} ser um subconjunto convexo fechado não vazio de Rn. Então existe um único vetor em {estilo de exibição K} de norma mínima (comprimento).

Prova do lema: Deixar {displaystyle delta =inf{|x|:por favor KY}.} Deixar {estilo de exibição x_{j}} seja uma sequência em {estilo de exibição K} de tal modo que {estilo de exibição |x_{j}|para delta } . Observe que {estilo de exibição (x_{eu}+x_{j})/2} é em {estilo de exibição K} desde {estilo de exibição K} é convexo e assim {estilo de exibição |x_{eu}+x_{j}|^{2}geq 4delta ^{2}} . Desde {estilo de exibição |x_{eu}-x_{j}|^{2}=2|x_{eu}|^{2}+2|x_{j}|^{2}-|x_{eu}+x_{j}|^{2}leq 2|x_{eu}|^{2}+2|x_{j}|^{2}-4delta ^{2}para 0} Como {estilo de exibição eu,jto infty } , {estilo de exibição x_{eu}} é uma sequência de Cauchy e, portanto, tem limite x em {estilo de exibição K} . É único, pois se y está em {estilo de exibição K} e tem norma δ, então {estilo de exibição |x-y|^{2}leq 2|x|^{2}+2|y|^{2}-4delta ^{2}=0} e x = y. {quadrado de estilo de exibição } Prova do teorema: Dados conjuntos convexos não vazios disjuntos A, B, deixar {estilo de exibição K=A+(-B)={x-imida xin A,yin B}.} Desde {estilo de exibição -B} é convexo e a soma dos conjuntos convexos é convexo, {estilo de exibição K} é convexo. Pelo lema, o encerramento {estilo de exibição {overline {K}}} do {estilo de exibição K} , que é convexo, contém um vetor {estilo de exibição v} de norma mínima. Desde {estilo de exibição {overline {K}}} é convexo, para qualquer {estilo de exibição m} dentro {estilo de exibição K} , o segmento de linha {estilo de exibição v+t(n-v),,0leq tleq 1} encontra-se em {estilo de exibição {overline {K}}} e entao {estilo de exibição |v|^{2}leq |v+t(n-v)|^{2}=|v|^{2}+2comemorar v,n-vrangle +t^{2}|n-v|^{2}} .

Por {estilo de exibição 0c_{2},{texto{ e }}ângulo y,contorcendo-se c,{texto{ e }}ângulo y,vrangle leq c} para todo x em A e y em B. Se ambos os conjuntos estiverem abertos, então existe um vetor diferente de zero v e um número real {estilo de exibição c} de tal modo que {estilo de exibição lang x,vrangle >c,{texto{ e }}ângulo y,contorcendo-se 0,ygeq 1/x}. } (Embora, por uma instância do segundo teorema, existe um hiperplano que separa seus interiores.) Outro tipo de contra-exemplo tem A compacto e B aberto. Por exemplo, A pode ser um quadrado fechado e B pode ser um quadrado aberto que toca A.

Na primeira versão do teorema, evidentemente, o hiperplano de separação nunca é único. Na segunda versão, pode ou não ser único. Tecnicamente, um eixo de separação nunca é único porque pode ser traduzido; na segunda versão do teorema, um eixo de separação pode ser único até a translação.

Use in collision detection The separating axis theorem (SENTADO) diz que: Dois objetos convexos não se sobrepõem se existir uma linha (chamado eixo) em que as projeções dos dois objetos não se sobrepõem.

SAT sugere um algoritmo para testar se dois sólidos convexos se cruzam ou não.

Independentemente da dimensão, o eixo de separação é sempre uma linha. Por exemplo, em 3D, o espaço é separado por planos, mas o eixo de separação é perpendicular ao plano de separação.

O teorema do eixo de separação pode ser aplicado para detecção rápida de colisão entre malhas de polígonos. A direção normal ou de outro recurso de cada face é usada como um eixo de separação. Observe que isso produz possíveis eixos de separação, não separando linhas/planos.

Em 3D, o uso de normais de face sozinho não conseguirá separar alguns casos de não colisão de ponta a ponta. Eixos adicionais, consistindo dos produtos cruzados de pares de arestas, um tirado de cada objeto, é requerido.[6] Para maior eficiência, eixos paralelos podem ser calculados como um único eixo.

Veja também Lema de Farkas de cone duplo Teorema de Kirchberger Controle ótimo Notas ^ Hastie, Trevor; Tibshirani, Roberto; Friedman, Jerônimo (2008). The Elements of Statistical Learning : Mineração de dados, Inferência, e Previsão (PDF) (Second ed.). Nova york: Springer. pp. 129-135. ^ Witten, Ian H.; Franco, teixo; Salão, Marco A.; Amigo, Christopher J. (2016). Mineração de dados: Ferramentas e técnicas práticas de aprendizado de máquina (Fourth ed.). Morgan Kaufman. pp. 253-254. ISBN 9780128043578. ^ Deisenroth, Marc Peter; Faisal, UMA. Aldo; Ong, Cheng Soon (2020). Matemática para aprendizado de máquina. Cambridge University Press. pp. 337–338. ISBN 978-1-108-45514-5. ^ Boyd & Vandenberghe 2004, Exercício 2.22. ^ Haim Brezis, Analyse fonctionnelle : teoria e aplicações, 1983, observação 4, p. 7. ^ "Matemática vetorial avançada". Referências Boyd, Estevão P.; Vandenberghe, Lieven (2004). Otimização Convexa (PDF). Cambridge University Press. ISBN 978-0-521-83378-3. Golstein, E. G.; Tretyakov, NV. (1996). Lagrangians modificados e mapas monótonos na otimização. Nova york: Wiley. p. 6. ISBN 0-471-54821-9. Shimizu, Kiyotaka; Ishizuka, Ei; Bardo, Jonathan F. (1997). Programação matemática não diferenciável e de dois níveis. Boston: Editores Acadêmicos Kluwer. p. 19. ISBN 0-7923-9821-1. External links Collision detection and response show vte Functional analysis (tópicos – glossário) mostrar espaços vetoriais topológicos vte (TV) Categorias: Teoremas em geometria convexaHermann Minkowski