Geometrí­a Computacional - Problemas - Cierres Convexos

Contents

1. Definición
2. Algoritmos
   1. Búsqueda de Aristas
   2. Búsqueda de Aristas de Jarvis (Más Inteligente)
   3. Algoritmo de barrido
   4. Algoritmo de Graham
   5. Algoritmo de Andrew
   6. Divide y Vencerás
3. Aproximación
   1. Aproximación por defecto
   2. Aproximación por exceso
4. Envolvente Convexa Ortogonal
   1. Definición: Conjunto Ortoconvexo
   2. Definición: Evolvente Convexa Ortogonal
   3. Hallar el Cierre Convexe de una Lista de Puntos
   4. Hallar el Cierre Convexe de una Lista de Puntos (Alternativa)
   5. Problema de las Farolas
5. Aplicaciones de Cierre Convexo
   1. Movimientos
   2. Calculo de la Recta Centro
   3. Cierre Convexo de Discos
   4. Expansión de Figuras
   5. Capas convexas
      1. Descripción
      2. Enlaces
6. Enlaces

Definición

Dado un polígono S, el cierre convexo es

• el polígono convexo que contiene a S y cuyos vértices son puntos de S
• el polígono de mayor área cuyos vértices están en S
• el polígono de menor perímetro que contiene a S
• la intersección de todos los conjuntos convexos que contienen a S
• la intersección de todos los semiplanos que contienen a S
• la intersección de todos los semiplanos cerrados que contiene a S y tienen algún punto de S en un borde
• la intersección de los semiplanos cerrados que contienen a S y tienen al menos 2 puntos de S en el borde (Como máximo hay n de ellos)

Algoritmos

Búsqueda de Aristas

Para cualquier par de puntos de S, Vi,Vj, se debe analizar si todos los demás están en el mismo semiplano respecto a ViVj:

Signo(Vi, Vj, Vk), k != i , k != j constante si es arista del CC

Output: Polígono convexo (lista ordenada de sus vértices)

Complejidad: O(n³)

Búsqueda de Aristas de Jarvis (Más Inteligente)

Dado una lista de puntos

• toma dos puntos (orden de entrada)
• El primero será el mas bajo.
• Con estos puntos, forma un segmento
• Si hay puntos a la derecha de estos, toma el más lejano, y rechaza los demás
• Repite la operación hasta se cierre el polígono

Complejidad: O(n²) O(n) por el número de aristas O(n) por el procesado de ellas Se puede asumir la complejidad como O(n * h) (h el numero de vértices del CC)

Algoritmo de barrido

• Ordenar los puntos de la izquierda a la derecha (O(nlogn))
• Cada punto aparece y desaparece a lo mas una vez (O(1))

Complejidad O(nlogn)

Algoritmo de Graham

Descripción

1. Toma los tres primeros puntos y halla el baricentro
2. Ordena los puntos del polígono angularmente respecto de este baricentro
3. Corre tras la lista ordenada de puntos eliminando los vertices que no son convexos

Complejidad O(nlogn)

• O(nlogn) para ordenar los puntos
• O(n) para correr tras la lista y eliminar vertices concavos (Utilizando un método inteligente con un stack)

Notas

• Peor caso de este algoritmo: Grand cantidad de puntos con los extremos formando un cuadrado.

Enlaces

• Mira el fin de la página

Algoritmo de Andrew

Dado una lista de puntos:

• Toma el mas a la izquierda y el mas a la derecha
• Divide el problema en dos, los puntos arriba y abajo del segmento
• Empieza a unir los puntos tres a tres para ver si el ángulo formado es cóncavo o convexo, primero en la parte de arriba y luego en la de abajo del segmento.
• Si el ángulo no es convexo, se debe hacer un retroceso y eliminar el punto de la solución final

El maximo será n-3 retrocesos

Complejidad: O(nlogn)

Divide y Vencerás

Descripción

• Divide el problema en dos según el número de datos y resuelvelos uno tras el otro
• Une dos polígonos, tomando el punto mas a la derecha del polígono izquierdo y el punto mas a la izquierda del pol´gono a la derecha.

(Tenga en cuenta que los segmentos posibles a unir no pueden cortar las aristas creadas.)

Complejidad: T(n) = O(nlogn)

• Dividir 2T(n/2)
• Mezclar O(n)

Aproximación

Aproximación por defecto

Trazo líneas equitativamente desde el punto más a la izquierda al más a la derecha de la sucesión de puntos, y de cada trozo obtenido, tomo el punto superior e inferior, con lo que reduzco drásticamente el numero de puntos iniciales. Después, hago el cierre convexo con el nuevo número de puntos. El problema surge cuando el número de franjas es muy pequeño por lo que es muy probable que el método falle, con lo que se tiene que comprobar todos los puntos para ver si están fuera o dentro del polígono y así asegurar que es un buen modelo. La peor situación es aquella en la que se tiene puntos que forman un circulo. La complejidad del algoritmo sería O(n) par la toma de puntos en la franja, más O ( franjas*2) para el nuevo cierre convexo.

Aproximación por exceso

Es semejante al caso anterior pero a la hora de tomar los puntos superior e inferior de cada franja, trazo una recta perpendicular a las líneas equitativas trazadas que pasen por el punto superior e inferior respectivamente, y tomo los dos puntos de corte generados entre la rectas y las líneas perpendiculares a ellas (2 para la parte superior y dos para la inferior). Después calculo el nuevo cierre convexo, aunque se debe tener en cuenta que el cierre convexo calculado, nunca va a ser el cierre convexo pedido dados los puntos distintos a los originales.

Envolvente Convexa Ortogonal

Definición: Conjunto Ortoconvexo

Es un "segmento" que conecta puntos en el conjunto de una manera que el "segmento" sea un camino ortogonal mínimo o una "escalera".

Definición: Evolvente Convexa Ortogonal

• La envolvente convexa ortogonal es aquella en la que una recta que pasa por dos puntos cualesquiera no entra mas de una vez en el polígono.
• Caminos ortogonales que encierran a todos los puntos con áreas mínimas.
• Para que un punto pueda ser envolvente convexo no debe tener ningún punto en alguno de los 4 cuadrantes que se forman al trazar una cruz con centro en dicho punto.

Hallar el Cierre Convexe de una Lista de Puntos

Fuerza bruto (probando lo anterior con todos los puntos) Complejidad: O(n²)

Hallar el Cierre Convexe de una Lista de Puntos (Alternativa)

• Ordenar los puntos de la izquierda a la derecha (o viceversa)
• Toma el de mas a la derecha y miro si el que está a su izquierda es mas alto que el
• Si lo es, le tomas
• Si no, no

(Así sucesivamente hasta llegar al punto mas alto, tendiendo una de las cuatro cadenas escalera posibles) *Haga lo mismo para las otras tres cadenas escalera

Complejidad O(nlogn)

• n para la comprobación
• logn para la ordenación

Este algoritmo tambien se puede utilizar para resolver el problema de Maxgap (distancia máxima entre dos puntos consecutivos una vez ordenados) y el problema de las farolas.

Problema de las Farolas

Dado un punto y un conjunto de puntos (farolas), ¿cuando está bien iluminado?

Para que un punto esté bien iluminado...

• debe tener puntos de luz por sus cuatro costados.
• debe ser dentro de la envolvente convexa

Una buena solución sería preprocesar el conjunto s = {P1,...Pn)} para que podemos responder en tiempo O(logn) si un punto está bien iluminado.

Otras variantes de este problema:

• Dadas n farolas y k puntos, averiguar si están todas bien iluminadas. Bastaría con calcular el cierre convexo y probarlo con los k puntos pedidos (Complejidad: O(nlogn + klogn))
• Dadas farolas, hallar si un segmento está bien iluminado. Habría que ver si el segmento está contenido en el CC.
• Como es la envolvente ortoconvexa de un segmento?
• Algoritmo O(n) para hallar la envolvente ortoconvexa de un polígono ortogonal

No se puede hallar la envolvente ortoconvexa en menos de O(nlogn) en el peor caso por que sirve para ordenar.

Aplicaciones de Cierre Convexo

Movimientos

Problema: Hay que ver si un piano cabe por una puerta haciendo una única translación.

1. Calcular el cierre convexo de la figura a mover
2. Calcular las rectas soporte del objeto con los puntos superior e inferior de la puerta.

Si las rectas se cortan, el objeto no entrará por la puerta, si son paralelas, entrará rozando, y si no se cortan y no son paralelas, entrará sin problemas.

Complejidad: O(n)

Problema: Hay que ver si un piano cabe por una puerta haciendo un giro y dos translaciones. Para el caso de un giro, primero debería tomar la perpendicular a la puerta y calcular la anchura del objeto (con el área signada). Después, unir las rectas perpendicular a la puerta con la de la anchura y mirar el ángulo que forman. Después girar hasta que el objeto entre.

Calculo de la Recta Centro

• Recta que mejor aproxima un conjunto de puntos
• Recta que minimiza la máxima distancia a los puntos

Hay que hallar el cierre convexo que contenga a una lista de puntos, y calcular la anchura del cierre convexo.

Complejidad: O(nlogn)

Cierre Convexo de Discos

• Calcular el cierre convexo de los centros de los discos
• calcular con los centros (que forman parte del CC) las tangentes de los discos

Expansión de Figuras

Semejante al problema del CC de discos.

Capas convexas

Descripción

• Uno o varios cierres convexos de un cierre convexo
• Hay que hallar el cierre convexo de una lista de puntos, y después de los puntos que no forman parte del cierre convexo hasta que no queden puntos o solo uno que sería el ultimo cierre convexo.

El algoritmo se usa en estadística para eliminar elementos anómalos (eliminar porcentajes de capas convexas). El algoritmo se puede hacer en tiempo n²logn, o bien, en tiempo nlogn con el algoritmo de Chazelle.

Enlaces

• Chazelle en Wikipedia [Link]
• Página oficial del Señor Chazelle [Link]

Enlaces

Página web sobre el tema cierres convexos (en inglés) descriebiendo... [Link]

• Cierres Convexos
• Complejidad de varios algoritmos
• Descripción de los algoritmos de Graham y Andrew
• Implementaciones y Referencias