Teorema del hiperplano de separación
En geometría, el teorema del hiperplano de separación es un enunciado sobre formas convexas disjuntas en el espacio euclídeo de n dimensiones. Hay varias versiones bastante similares. En una versión del teorema, si ambos conjuntos son disjuntos, cerrados y al menos uno de ellos es compacto, entonces existe un hiperplano entre ellos e incluso dos hiperplanos paralelos entre ellos separados por un espacio. En otra versión, si ambos conjuntos convexos disjuntos están abiertos, entonces existe un hiperplano entre ellos, pero no necesariamente un espacio. Un eje que es ortogonal a un hiperplano de separación es un eje de separación, porque las proyecciones ortogonales de los cuerpos convexos sobre el eje son disjuntos.
Teorema del hiperplano de separación | ||
---|---|---|
![]() Ilustración del teorema del hiperplano de separación | ||
Tipo | Teorema | |
Campo | ||
Conjeturado por | Hermann Minkowski | |
Problema abierto | No | |
Generalizaciones | Teorema de separación de Hahn-Banach | |
El teorema de separación de hiperplanos se debe a Hermann Minkowski. Por otro lado, el teorema de Hahn–Banach generaliza el resultado a espacios vectoriales topológicos.
Un resultado relacionado es el del teorema del hiperplano de soporte.
En el contexto de máquinas de vectores de soporte, el hiperplano de separación óptima o el hiperplano de margen máximo es aquel hiperplano que separa las envolventes convexas de dos conjuntos de puntos, y es equidistante de ambas.[1][2][3]
Declaraciones y demostraciones
|
En todos los casos, se supone que son subconjuntos disjuntos, no vacíos y convexos de
. El resumen de los resultados es el siguiente:
Compacto cerrado | Cerrado | ||
Cerrado | Compacto cerrado | ||
Abierto | |||
Abierto | Abierto |
El número de dimensiones debe ser finito. En espacios de dimensión infinita hay ejemplos de dos conjuntos cerrados, convexos y disjuntos que no pueden separarse por un hiperplano cerrado (un hiperplano donde un funcional lineal continuo es igual a alguna constante), incluso en el sentido débil donde las desigualdades no son estrictas.[4]
Aquí no se puede relajar la hipótesis de compacidad; véase un ejemplo en la sección contraejemplos y unicidad. Esta versión del teorema de separación se generaliza a dimensiones infinitas; la generalización se conoce más comúnmente como teorema de separación de Hahn-Banach.
La demostración se basa en el siguiente lema:
|
Demostración |
Sean |
![](http://upload.wikimedia.org/wikipedia/commons/thumb/7/7c/Separating_Hyperplanes_Theorem.png/220px-Separating_Hyperplanes_Theorem.png)
Demostración |
Primero se demuestra el segundo caso (véase el diagrama). Sin pérdida de generalidad, Como Algebraicamente, los hiperplanos Supongamos que hay algún A continuación se demuestra el primer caso. Acérquese a ambos conjuntos Ahora, en el segundo caso, para cada par Como la esfera unitaria es compacta, se puede tomar una subsecuencia convergente, de modo que Supóngase que esto no es así. Entonces, existe algún |
Dado que un hiperplano de separación no puede intersecar los interiores de conjuntos convexos abiertos, se deduce el corolario siguiente:
|
Caso con posibles intersecciones
Si los conjuntos tienen posibles intersecciones, pero sus interiores relativos son disjuntos, entonces la prueba del primer caso aún se aplica sin cambios, lo que produce:
|
en particular, se tiene el hiperplano de soporte.
|
Demostración |
Si el intervalo afín de |
Teorema recíproco
Téngase en cuenta que la existencia de un hiperplano que solo separa dos conjuntos convexos en el sentido débil de que ambas desigualdades no son estrictas, obviamente no implica que los dos conjuntos sean disjuntos. Ambos conjuntos podrían tener puntos ubicados en el hiperplano.
Contraejemplos y singularidad
![](http://upload.wikimedia.org/wikipedia/commons/thumb/9/99/Separating_axis_theorem2.svg/220px-Separating_axis_theorem2.svg.png)
Si uno de los conjuntos A o B no es convexo, entonces hay muchos contraejemplos posibles. Por ejemplo, A y B podrían ser círculos concéntricos. Un contraejemplo más sutil es aquel en el que A y B son cerrados pero ninguno es compacto. Por ejemplo, si A es un semiplano cerrado y B está delimitado por un brazo de una hipérbola, entonces no existe un hiperplano de separación estricta:
(aunque, por un ejemplo del segundo teorema, existe un hiperplano que separa sus interiores). En otro tipo de contraejemplo se tiene que A es compacto y B es abierto. Por ejemplo, A puede ser un cuadrado cerrado y B puede ser un cuadrado abierto que toca a A.
En la primera versión del teorema, evidentemente el hiperplano de separación nunca es único. En la segunda versión, puede ser único o no. Técnicamente, un eje de separación nunca es único porque se le puede aplicar una traslación; en la segunda versión del teorema, un eje de separación puede ser único sin necesidad de obviar traslaciones.
El ángulo abocinado proporciona un buen contraejemplo para muchas separaciones de hiperplanos. Por ejemplo, en , el disco unitario está separado del intervalo abierto
, pero la única recta que los separa contiene la totalidad de
. Esto muestra que si
está cerrado y
está relativamente abierto, entonces no existe necesariamente una separación estricta para
. Sin embargo, si
está cerrado como politopo, entonces existe dicha separación.[5]
Más variantes
El lema de Farkas y los resultados relacionados pueden entenderse como teoremas de separación de hiperplanos cuando los cuerpos convexos están definidos por un número finito de desigualdades lineales.
Se pueden encontrar más resultados sobre conjuntos convexos disjuntos.[5]
Uso en la detección de colisiones
En la detección de colisiones, el teorema de separación de hiperplanos se suele utilizar de la siguiente forma:
|
Independientemente de la dimensión considerada, el eje de separación es siempre una línea recta. Por ejemplo, en 3D, el espacio está separado por planos, pero el eje de separación es perpendicular al plano de separación.
El teorema del eje de separación se puede aplicar para la detección de colisiones rápida entre mallas poligonales. Las normales de cada cara o cualquier otra dirección de un elemento se utiliza como eje de separación. Téngase en cuenta que esto produce posibles ejes de separación, no líneas/planos de separación.
En 3D, el uso exclusivo de normales a las caras no logrará separar algunos casos de borde a borde que no colisionan. Se requieren ejes adicionales, que consisten en los productos cruzados de pares de aristas, una tomada de cada objeto.[6]
Para aumentar la eficiencia, los ejes paralelos se pueden calcular como un solo eje.
Véase también
- Cono dual
- Lema de Farkas
- Teorema de Kirchberger
- Control óptimo