algorithm - El perímetro mínimo del casco convexo de un subconjunto de un conjunto de puntos
computational-geometry convex-hull (4)
Dados n puntos en el plano. No 3 son colineales.
Dado el número k.
Encuentre el subconjunto de puntos k, de manera que el casco convexo de los puntos k tenga un perímetro mínimo fuera de cualquier casco convexo de un subconjunto de puntos k.
Se me ocurre un método ingenuo que se ejecuta en O (n ^ kk log k). (Encuentre el casco convexo de cada subconjunto de tamaño k y obtenga el mínimo).
Creo que este es un problema de NP, pero no puedo encontrar nada adecuado para su reducción.
¿Alguien tiene ideas sobre este problema?
Un ejemplo,
the set of n=4 points {(0,0), (0,1), (1,0), (2,2)} and k=3
Resultado:
{(0,0),(0,1),(1,0)}
Como este conjunto contiene 3 puntos, el casco convexo y el perímetro del resultado es más pequeño que el de cualquier otro conjunto de 3 puntos.
En el caso plano, puede usar un algoritmo conocido como la marcha de Jarvis, que tiene la complejidad del caso O (n ^ 2). En este algoritmo, comienza a construir un casco en un punto arbitrario y luego verifica qué punto se debe agregar a continuación. Pseudocódigo tomado de wikipedia :
jarvis(S)
pointOnHull = leftmost point in S
i = 0
repeat
P[i] = pointOnHull
endpoint = S[0] // initial endpoint for a candidate edge on the hull
for j from 1 to |S|-1
if (S[j] is on left of line from P[i] to endpoint)
endpoint = S[j] // found greater left turn, update endpoint
i = i+1
pointOnHull = endpoint
until endpoint == P[0] // wrapped around to first hull point
Por lo que yo entiendo, los cascos convexos son únicos para cada conjunto de puntos, por lo que no hay necesidad de encontrar un mínimo. Solo encuentra uno, y será el más pequeño por definición.
Editar
La solución publicada resuelve el casco convexo con la menor cantidad de puntos. Cualquier casco con más puntos tendrá un perímetro más largo, y malinterpreté la pregunta de buscar un perímetro mínimo, en lugar de un perímetro mínimo para un conjunto con K puntos.
Este nuevo problema probablemente sea NP como se sospecha, y más similar al problema de la ruta más larga. Desafortunadamente, me falta el ingenio para proporcionar una reducción valiosa.
Esto se puede hacer en O (kn ^ 3) tiempo y O (kn ^ 2) espacio (o tal vez O (kn ^ 3) si desea los puntos reales).
Este documento: http://www.win.tue.nl/~gwoegi/papers/area-k-gons.pdf
por Eppstein et al, tiene algoritmos para resolver este problema para el perímetro mínimo y otras funciones de peso como área, suma de ángulos internos, etc. que siguen ciertas restricciones, aunque el título dice área mínima (vea el Corolario 5.3 para el perímetro).
La idea básica es un enfoque de programación dinámica como sigue (lea los primeros párrafos de la Sección 4):
Supongamos que S es el conjunto de puntos dado y Q es el casco convexo de k puntos con un perímetro mínimo.
Sea p1 el punto más bajo de Q, p2 y p3 son los siguientes puntos en el casco en el sentido contrario a las agujas del reloj.
Podemos descomponer Q en un triángulo p1p2p3 y un casco convexo de k-1 puntos Q ''(que comparte el lado p1p3 con el triángulo p1p2p3).
La observación principal es que Q ''es el óptimo para k-1, en el que el punto más bajo es p1 y el siguiente punto es p3 y todos los puntos de Q'' se encuentran en el mismo lado de la línea p2-> p3.
De este modo, se mantiene una matriz 4d de polígonos óptimos para cada cuádruple (pi, pj, pk, m) de manera que
- el polígono es un casco convexo de exactamente m puntos de S.
- pi es el punto más bajo del polígono.
- pj es el siguiente vértice en el orden contrario a las agujas del reloj,
- todos los puntos del polígono se encuentran a la izquierda de la línea pi -> pj.
- todos los puntos se encuentran en el mismo lado de pj-> pk como lo hace pi.
puede ayudarnos a encontrar los polígonos óptimos para m = k, dados los polígonos óptimos para m <= k-1.
El documento describe exactamente cómo hacerlo para lograr los límites de tiempo y espacio establecidos.
Espero que ayude.
No es exactamente una solución bonita. De hecho, es bastante difícil de implementar, pero seguramente le da complejidad polinómica. Aunque la complejidad también es grande (n ^ 5 * k es mi estimación aproximada), alguien puede encontrar una manera de mejorarla o encontrar aquí una idea para una mejor solución. O puede ser suficiente para usted: incluso esta complejidad es mucho mejor que la fuerza bruta.
Nota : la solución óptima (conjunto S ) con casco H incluye todos los puntos del conjunto original dentro de H De lo contrario, podríamos tirar uno de los puntos de borde de H e incluir ese punto perdido, reduciendo el perímetro.
( Actualizar justo como ''optimización'' mbeckish publicado)
Supuesto : no hay dos puntos del conjunto que formen una línea vertical. Se puede lograr fácilmente girando todo el conjunto de puntos mediante algún ángulo irracional alrededor del origen de las coordenadas.
Debido a la suposición anterior, cualquier casco complejo tiene un punto situado más a la izquierda y uno más a la derecha. Además, estos dos puntos dividen el casco en top partes top e bottom .
Ahora, tomemos un segmento de la parte top de este casco y uno de la parte bottom . Llamemos a esos dos segmentos segmentos middle segments y perímetro de la parte derecha de este casco - perímetro right .
Nota : esos dos segmentos es todo lo que necesitamos saber sobre la parte derecha de nuestro casco convexo para continuar construyéndolo hacia la izquierda. Pero tener solo dos puntos en lugar de 4 no es suficiente: no podríamos mantener la condición de "convexidad" de esta manera.
Conduce a una solución . Para cada conjunto de puntos {p0, p1, p2, p3} y el número i (i <= k) almacenamos right perímetro right mínimo que puede lograrse si [p0, p1], [p2, p3] son dos segmentos middle i es el número de puntos en la parte right de esta solución (incluidos los que están dentro de ella, no solo en el borde).
Pasamos por todos los puntos de derecha a izquierda. Para cada nuevo punto p , verificamos todas las combinaciones de puntos {p0, p1, p2, p3} de modo que el punto p pueda continuar este casco hacia la izquierda (ya sea en la top o en la parte bottom ). Para cada conjunto y tamaño i , ya almacenamos el tamaño óptimo del perímetro (ver el párrafo anterior).
Nota : si agrega el punto p a un right-hull formado por los puntos {p0, p1, p2, p3}, incrementará el tamaño del conjunto i al menos en 1. Pero a veces este número será> 1: tendrá para incluir todos los puntos en el triángulo {p, p0, p2}. No están en el casco, pero dentro de él.
El algoritmo ha terminado :) Además, a pesar de la complejidad del miedo, puede observar que no todos los segmentos [p0, p1], [p2, p3] pueden ser segmentos middle : debe reducir sustancialmente el tiempo de cálculo real.
Actualizar Esto proporciona solo el tamaño óptimo del perímetro, no el conjunto en sí. Pero encontrar el conjunto es simple: para cada ''estado'' anterior no solo almacena el tamaño del perímetro, sino también el último punto agregado. Entonces, puedes "rastrear" tu solución de vuelta. Es un truco bastante estándar, supongo que no es un problema para ti, parece que eres bueno en los algoritmos :)
update2 Esto es esencialmente DP (programación dinámica), solo un poco hinchado
Una posible optimización: puede ignorar cualquier subconjunto cuyo casco convexo contenga puntos que no estén en el subconjunto.
Prueba:
Si su casco convexo contiene puntos que no están en su subconjunto, entonces elimine un punto de su subconjunto que está en el casco y reemplácelo con un punto en el interior del casco. Esto producirá un casco de perímetro igual o menor.