dado um polígono convexo e um número N, como faço para encontrar o menor polígono que

contém todos os pontos do polígono originaltem exatamente N pontos de canto

Por exemplo, suponha que eu tenha um conjunto de pontos e calcule o casco convexo para eles (verde). Agora eu quero encontrar o menor quadrilátero que contém todos os pontos (vermelho)

É fácil ver que qualquer outro polígono com 4 cantos seria maior ou não conteria todos os pontos. Mas como eu encontro esse polígono no caso geral?

EDITAR:

Com o menor polígono quero dizer o que cobre a menor área, embora eu não tenha certeza se a menor circunferência daria resultados diferentes.

Adicionei mais duas imagens de exemplo que, infelizmente, parecem não funcionar com a abordagem "remover bordas" em uma das respostas

Algumas informações básicas:

O objetivo é determinar com precisão as formas com reconhecimento de imagem. Por exemplo, tire uma foto de um cubóide. Todos os pontos dentro da caixa na foto 2D estarão contidos em um polígono convexo de 6 cantos. No entanto, como as formas do mundo real não têm cantos perfeitos e a câmera adiciona um pouco de desfoque, as bordas desse polígono serão arredondadas. Veja a imagem anexada da perguntaObtendo cantos de pontos convexos