Generating a minimal convex polygon

So I'd like to generate a convex polygon around a set of points, where the number of vertices is an input. I'm aware of convexhull, but this produces far too many vertices for my needs. I'd like a convex polygon (with the smallest area possible) that surrounds all my points (or the convex hull, same thing). For example, If I had 2-D data points that form a circle, and I want a 5 vertex polygon, you can imagine that it would look like an equal sided pentagon tangent to the circle in 5 places. Any ideas? Thanks

Answer 1

[Image Analyst]

I think Mark might like John D'Errico's very nice suite of minimally bounding shapes: http://www.mathworks.com/matlabcentral/fileexchange/34767-a-suite-of-minimal-bounding-objects. Mark can pick the shape he's interested in.

Answer 2

[Boris Blagojevic]

In case someone stumbles over this:

An easy alternative is using hull = convull(Points,'Simplify',true). All Points which add no area are neglected with this. I think that is quite what was asked for.

[Image Analyst]

That's a nice feature. It won't however turn a circle into a pentagon (the example the original poster mentioned). For that, or for situations where the shape is not convex, one might refer to the attached paper on "minimum perimeter polygon".

Answer 3

[John D'Errico]

You have stated an ill-posed problem, because your goals are not clear. Clearly THE minimal convex polygon is the convex hull. But you are asking for the minimal convex polygon with n vertices, where n<H, the number of vertices of the convex hull. Is n fixed? If not, then what measure is used to choose n?

Even if n is fixed, it is not clear what the best scheme is. For some values of n, it is likely that the minimal enclosing polygon has some edges that are coincident with edges of the convex hull, but choosing those edges may be difficult.

And if the enclosed object is some completely general closed, smooth form, the problem is now more difficult yet.

Sorry, but you need to define your goals more clearly, and make those goals have a snowball's chance in Texas to represent a solvable problem.

Answer 4

[arich82]

It seems like you've already eaten the computational cost of finding the 2-D convex hall (resulting in a convex n-gon). It sounds like, for a given number of vertices k, you're asking to find the minimum circumscribing convex k-gon, where k<n.

This is not a trivial problem, unless k=3.

See if Aggarwal et. al (1985) [and references therein] might be helpful: http://link.springer.com/article/10.1007%252FBF01898354. They report to have an order O(n^2 log(n) log(k)) algorithm, though they don't seem to claim optimality.

Note: If you have a more structured problem, e.g. you're just looking to identify a box with long edges but there are some rounded corners artificially increasing n, then you could likely devise a simple algorithm to eliminate sides below a certain threshhold length, and extend their neighbors to intersect; note that this wouldn't gurantee a minimal solution, but might be a practical one.