No estoy seguro de si esta pregunta debe hacerse aquí o en math.stackexchange.
Se puede suponer que todos los vértices son únicos. Los vértices dados pueden ser los vértices del polígono, por lo tanto NO tienen que estar dentro del polígono, pero NO deben estar fuera del polígono (y creo que para obtener el polígono de área mínima, deben ser los vértices del polígono). El polígono puede ser cóncavo.
Estoy pensando en utilizar el algoritmo del casco convexo como primer paso, y luego desde cada arista del polígono del casco convexo, "excavo" eliminando una arista del polígono mencionado (que la arista conecte vértice a y vértice b ), y crear 2 nuevas aristas ( a-c y c-b ) donde c es un vértice que anteriormente estaba situado dentro del polígono. Y hacerlo hasta que no quede ninguna arista dentro del polígono (es decir, todos los vértices se han convertido en vértices del polígono). Pero no tengo la "excavación en" algo que se ha demostrado para minimizar el área del polígono.
Como pregunta al margen, ¿se trata de un problema NP-completo?
