El casco convexo de perímetro mínimo de un subconjunto de un conjunto de puntos
Dados n puntos en el avión. No 3 son colineales.
Dado el número k.
Encuentre el subconjunto de k puntos, de modo que el casco convexo de los k puntos tenga un perímetro mínimo fuera de cualquier casco convexo de un subconjunto de k puntos.
Puedo pensar en un método ingenuo que se ejecuta en O (n ^ k k log k). (Encuentre el casco convexo de cada subconjunto de tamaño k y genere el mínimo).
Creo que este es un problema de NP, pero no puedo encontrar nada adecuado para reducirlo.
¿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)}
Dado que 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.