# Generating a minimal convex polygon

21 views (last 30 days)

Show older comments

##### 0 Comments

### Answers (4)

Image Analyst
on 19 Feb 2014

##### 0 Comments

Boris Blagojevic
on 17 May 2021

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.

##### 1 Comment

Image Analyst
on 18 May 2021

John D'Errico
on 18 Feb 2014

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.

##### 0 Comments

arich82
on 19 Feb 2014

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.

##### 0 Comments

### See Also

### Categories

### Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!