encontrar el polígono convexo que contiene más pequeño con un número determinado de puntos

Question

dado un polgyon convexo y un número N, ¿cómo puedo encontrar el polígono más pequeño que

1. contiene todos los puntos del polígono original,
2. tiene exactamente N puntos de esquina

Por ejemplo, supongamos que tengo un conjunto de puntos y calculo el casco convexo para ellos (verde). Ahora quiero encontrar el cuadrilátero más pequeño que contiene todos los puntos (rojo)

Es fácil ver que cualquier otro polígono con 4 esquinas actuación sea más grande o no logran contener todos los puntos . ¿Pero cómo encuentro este polígono en el caso general?

---

EDIT:

Con polígono más pequeño me refiero a la la que cubre el área más pequeña, aunque no estoy seguro de si la circunferencia más pequeña podría dar resultados diferentes.

he añadido dos más imágenes de ejemplo que, lamentablemente, no parecen trabajar con el enfoque de 'eliminar los bordes' en una de las respuestas

---

Algunos antecedentes:

El objetivo es determinar con precisión formas con reconocimiento de imagen. Por ejemplo, tome una foto de un paralelepípedo. Todos los puntos dentro de la caja en la foto 2D estarán contenidos en un polígono convexo de 6 esquinas. Sin embargo, dado que las formas del mundo real no tienen esquinas perfectas, y la cámara agrega un poco de desenfoque, los bordes de este polígono se redondearán. Ver la imagen adjunta de la cuestión Getting corners from convex points

Answer 1

es necesario definir el concepto de "más pequeño" en su pregunta. Cualquiera que sea su definición, esta pregunta ha sido muy estudiada en la literatura sobre geometría computacional. La frase clave de búsqueda es encierra un mínimo k-gon:

• Mictchell et al .: "mínimo-Perímetro Encerrando k-gon" 2006 (CiteSeer link)
• Aggarwal et al .: "Área mínima Circumscribe polígonos" 1985 (CiteSeer link)
• O'Rourke et al .: "Un algoritmo óptimo para fnding triángulos de cerramiento mínimos" 1986, Algorithmica (ACM link)

Los algoritmos generales no son simples (aunque los algoritmos para triángulos o rectángulos de área mínima son simples). Dependiendo de sus objetivos, es posible que deba abandonar cualquier noción matemática de "más pequeña" y dirigirse a una heurística.

Answer 2

While number of edges > N do 
    remove the shortest edge by replacing its endpoints 
    with the intersection point of the adjacent edges