find the smallest containing convex polygon with a

问题:

given a convex polgyon and a number N, how do I find the smallest polygon that

1. contains every point from the original polygon
2. has exactly N corner points

For example, suppose I have a set of points and compute the convex hull for them (green). Now I want to find the smallest quadrangle that contains all the points (red)

It is easy to see that any other polygon with 4 corners would either be bigger or fail to contain all the points. But how do I find this polygon in the general case?

---

EDIT:

With smallest polygon I mean the the one that covers the smallest area, although I am not sure whether the smallest circumference would give different results.

I added two more example pictures that unfortunately do not seem to work with the 'remove edges' approach in one of the answers

---

Some background information:

The goal is to accurately determine shapes with image recognition. For example take a foto of a cuboid. All points inside the box in the 2D-photo will be contained in a 6-corner convex polygon. However since real-world shapes do not have perfect corners, and the camera adds some blur, the edges of this polygon will be rounded. See the attached image from the question Getting corners from convex points

回答1:

You need to define the notion of "smallest" in your question. Whatever your definition, this question has been heavily studied in the computational geometry literature. The key search phrase is minimal enclosing k-gon:

• Mictchell et al.: "Minimum-Perimeter Enclosing k-gon" 2006 (CiteSeer link)
• Aggarwal et al.: "Minimum Area Circumscribing Polygons" 1985 (CiteSeer link)
• O'Rourke et al.: "An optimal algorithm for fnding minimal enclosing triangles" 1986, Algorithmica (ACM link)

The general algorithms are not simple (although algorithms for min area triangles or rectangles are simple). Depending on your goals, you might have to abandon any mathematical notion of "smallest" and head for a heuristic.

回答2:

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