find the smallest containing convex polygon with a given number of points

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

Answers


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.


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

Need Your Help

DST file reader for iOS

iphone ios ios4 ios5 file-format

I have a requirement to write an iOS app that can read and edit PDF files. I am confused where to start digging. Please shed some light on where should I start and what all technologies I should us...

How to insert multiple/different hidden fields into XML?

javascript xml arrays jsp hidden

I need to insert multiple hidden fields(data) into the XML. Currently, I can only insert one data at one time. Let's say that I have a few 'tiles'(which contains multiple coordinates) to insert int...