¿Cuáles son las aplicaciones de la vida real de los cascos convexos?

Answer 1

Una de las aplicaciones geniales de los cascos convexos es el cálculo / construcción de relajaciones convexas. Hablando en términos generales, esta es una manera de encontrar el problema convexo “más cercano” a un problema no convexo que está intentando resolver. Si bien podría definir esto formalmente, creo que una imagen simple podría ser más interesante.

Supongamos que queremos resolver un problema cuya superficie de restricción es esta cosa fea:

Los puntos amarillos representan las posibles soluciones enteras que se encuentran en esta superficie. Esto es feo y tiene toneladas de mínimos. Pero, si miramos alrededor de los verdaderos mínimos globales, vemos que podríamos construir una restricción convexa que ‘cubra’ esta superficie:

Ahora, una forma de construir tal relajación (al menos conceptualmente) es tomar el casco convexo de todos los mínimos (locales y globales). En este caso, tenemos una superficie convexa que contiene nuestros verdaderos mínimos globales y, por lo tanto, hemos “relajado” el problema a una configuración convexa. Obviamente, esto no siempre es posible en situaciones prácticas (fuera de los objetivos simples 1D, [matemática] C ^ {2} [/ matemática] con grandes límites inferiores en la curvatura), pero es una buena manera de demostrar teoremas sobre convexidad relajaciones Hay muchas relajaciones convexas famosas para problemas de números enteros (por ejemplo, k-SAT, programas lineales enteros) y muchos algoritmos aproximados y / o probabilísticos que se usan en la práctica dependen en gran medida de esta técnica.

Crédito de la imagen: relajación convexa

Answer 2

Esta no es necesariamente una aplicación de optimización, pero los cascos convexos se pueden usar en el procesamiento de imágenes. En particular, la función ‘regionprops’ en matlab puede darle los puntos en el polígono convexo más pequeño que puede contener el objeto detectado. Esto puede ser útil si quiere, por ejemplo, concentrarse en la región que rodea el objeto si no tiene una forma convexa.

Answer 3

En la cocina , puede usar un conjunto de recetas para el mismo plato para descubrir un casco convexo de ingredientes.

Leer más: Cocina para nerds: ingrediente poliedro y casco convexo

Answer 4

Lo bueno de los cascos convexos es que las pruebas internas / externas y las métricas de distancia que utilizan medios espacios son triviales. Por lo tanto, se utilizan en la detección de colisiones para simulaciones físicas.

Primero, un casco convexo de un objeto complejo puede usarse como una geometría muy simplificada para una detección de colisión de “fase amplia” muy rápida.
Si no se supera esa prueba, dos objetos definitivamente no chocan y podemos omitir el costoso siguiente paso. Aprobar el examen significa que tenemos que hacer más trabajo.

A continuación, cualquier objeto complejo (cóncavo) puede descomponerse en una colección de objetos convexos. Y estos pueden ser probados contra aquellos en el otro objeto para un algoritmo de detección de colisión perfecto.

Answer 5

Se utiliza en la planificación del movimiento del robot:

Para pasar de s a t, la ruta más corta será la línea recta de s a t (si el obstáculo no se cruza con ella) o una de las dos cadenas poligonales del casco convexo.

Answer 6

Además de todas las aplicaciones ya mencionadas, el casco convexo también tiene las siguientes aplicaciones:

1. Evacuación de fugas nucleares / químicas. Imagine una ciudad moderna con censores posicionados uniformemente por todas partes. Cuando ocurre un desastre, como una fuga química o una fuga de radiación nuclear, una forma de determinar el perímetro para la evacuación inmediata es construir el casco convexo de las áreas con niveles de radiación (que exceden un cierto umbral.
2. Seguimiento de la epidemia de enfermedades . Se podría realizar un seguimiento de la extensión espacial de un brote de enfermedad utilizando el casco convexo. Un ejemplo específico en el seguimiento de la epidemia de animales está disponible aquí: extensión espacial de un brote de epidemias de animales.
3. Programacion Lineal . El algoritmo simplex en realidad encuentra el punto óptimo al iterar sobre los vértices del casco convexo (intersección de los medios espacios de restricción) construidos a partir de las restricciones lineales.
4. Bloque de construcción en otros problemas. Algunas de estas aplicaciones ya se han mencionado. Uno más para agregar es calcular el diámetro de un conjunto de puntos: la distancia entre los dos puntos más lejanos. Un paso de preprocesamiento es calcular primero el casco convexo y luego encontrar el par de puntos que están más alejados. Otro es calcular las capas convexas tomando repetidamente el casco convexo. Sin embargo, hay mejores algoritmos para este último.

Answer 7

Suponga que desea simplificar una imagen digital en una que use solo un pequeño conjunto de, por ejemplo, varios colores. Una forma de elegir esos colores es restringir sus elecciones a los colores de los vértices del casco convexo, en el espacio de color RGB o LAB, del conjunto de todos los colores en la imagen original. Es más probable que estos sean los colores “interesantes” más saturados en comparación con las mezclas de colores más opacas pero más comunes en la imagen. A menudo, necesita aplicar algunos clústeres previos en el espacio de color y luego aplicar esta técnica a cada grupo. Pero incluso sin eso funciona bien en muchos casos.

Answer 8

Al crear la incrustación Tutte de un gráfico, podemos elegir cualquier cara y convertirla en la cara externa (casco convexo) del dibujo, esa es la motivación central de la incrustación tutte.

Hay una reducción de tiempo polinomial del problema Simplex intermedio al problema de factorización simple (matriz) y viceversa. [Vavasis];
El objetivo de isp es encontrar un conjunto de puntos T que formen un símplex (es decir, T es un conjunto de r puntos afines independientes) cada uno en P (poliedro) de modo que el casco convexo de T contenga los puntos en S (un conjunto de m puntos [1]).

Al encontrar eficientemente la palabra que tiene una probabilidad distinta de cero solo en ese tema (palabras de anclaje) para el modelado / recuperación de temas bayesianos de los documentos.
[Si un documento contiene esta palabra de anclaje, se garantiza que el tema correspondiente se encuentra entre el conjunto de temas utilizados para generar el documento. [Arora et al]]

En el caso de datos infinitos donde tenemos infinitos documentos, el casco convexo de las filas en la matriz de momento normalizado de segundo orden de fila será un simplex donde los vértices de este simplex corresponden a las palabras de anclaje.

Los clasificadores óptimos para usos comunes de los clasificadores se encuentran en el ROC (gráfico de tasa positiva verdadera en función de la tasa de falsos positivos) Casco convexo. [Provost y Fawcett]
[1] [matemáticas] P = \ {x \ en R ^ {r-1}: Hx \ geq b \} [/ matemáticas]
H es [matemática] n \ veces {r-1} [/ matemática] y [matemática] b \ en R ^ n [/ matemática] tal que Hb tenga un rango r y [matemática] S \ en R ^ {r- 1} [/ matemáticas].

Answer 9

Si necesita cercar un conjunto de objetos, ubicaciones o áreas, utilizando tramos rectos de cerca (y minimizando la cantidad de cerca utilizada o el área cerrada), desea el casco convexo. Esto se relaciona con la respuesta de la robótica, ya que utiliza tramos rectos de franja de bordes para encerrar el área que limpiará una aspiradora robot.

Answer 10

Soy un estudiante universitario que acaba de comenzar un proyecto de investigación en computación cuántica (teórica). Estamos usando “programación semi-definida” [1], un subcampo de optimización convexa, para aproximar soluciones a (la energía del estado fundamental de) sistemas cuánticos que son computacionalmente difíciles de resolver exactamente.

[1] Programación semidefinida

Answer 11

Usos del casco convexo en el software de edición de imágenes, es decir, photoshop.

1. Varita mágica
2. Efecto de resplandor y sombra en la capa. Se puede entender mejor aplicando en una imagen no rectangular.
3. Haga una selección por Ctrl + clic en la capa.

Uso del algoritmo de casco convexo en la vida diaria por parte de nuestra mamá.

• Recolectando semillas de grano en el piso a mano o con batidor.

Uso del algoritmo de casco convexo por profesionales del clima para determinar el área de lluvia.

• Determine el área total de cascadas analizando todos los censores que envían señales de cascada usando el algoritmo de infierno convexo.