That is an important condition. I would imagine that the optimal polygon should have as many points on its edges as possible.
I wonder if you could do something like this: (I'm making this up as I go along and basing it off a diagram I drew on the back of a small receipt so it may be very wrong)
1. Find the center of the collection of points in P (by averaging all of the x- and y-coordinates), call this point C
2. Find the point furthest from the center, let that be a vertex in the N-gon. Call this point P1
3. Draw a horizontal line from P1. Find the point furthest from the horizonal (in terms of the line segment passing through that point and perpendicular to the horizontal) which is not on the same side of the horizontal as C. That is, if C is below the horizontal look for the point above the horizontal and vise-versa. If there is no such point, look for the point closest to the horizontal but on the same side as C. Call this point P2.
4. Let L1 be the line passing through P1 and P2.
At this point, if my imagination and the drawing I made on the back of a receipt are correct, L1 should divide the plane so that all points in P are on one side of L1. A segment of L1 will be an edge of the N-gon.
5. Repeat steps (3) and (4) but instead of a horizontal line from P1, draw a vertical line. Use this to find the point P3 and line L2.
You should now have two lines which contain edges of the N-gon as well as a vertex, P1. Unless all the points of P are colinear then the points P1, P2, and P3, should be distinct.
6. Find the point furthest from P1, call this P4. Note, P4 may not be distinct from P2 or P3.
7. Draw a line through P2 and P3 and call it L3.
8. Draw a line passing through P4 that is parallel to L3 and call this L4.
You should now have the smallest possible triangle which includes all of your points in P. This triangle is made by L1, L2, and L4. From here it should be a lot easier to find the smallest possible N-gon.
Need information on a function I've posted? Chances are it's at the MSDN