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

Contiene todos los puntos del polígono original.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 cuadrángulo más pequeño que contiene todos los puntos (rojo)

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

EDITAR:

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

Agregué dos imágenes de ejemplo más que, lamentablemente, no parecen funcionar con el enfoque 'eliminar bordes' en una de las respuestas

Alguna información de fondo:

El objetivo es determinar con precisión las formas con reconocimiento de imagen. Por ejemplo, tomar una foto de un cuboide. Todos los puntos dentro del cuadro 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 añade algo de desenfoque, los bordes de este polígono se redondearán. Ver la imagen adjunta de la pregunta.Consiguiendo esquinas a partir de puntos convexos.