Not sure whether this question belongs here or math.stackexchange.

You can assume that all the vertices are unique. The given vertices can be the vertices of the polygon, thus they do NOT have to be inside the polygon, but they must NOT be outside the polygon (and I think to get the minimum-area polygon, they must be the polygon vertices). The polygon can be concave.

I am thinking of using convex-hull algorithm as the first step, and then from each edge of the convex-hull polygon, I "dig in" by removing an edge from the aforementioned polygon (let the edge connects vertex *a* and vertex *b*), and create 2 new edges (*a-c* and *c-b*) where *c* is a vertex which was previously located inside the polygon. And do it until there is no more edge remaining inside the polygon (i.e all vertices have become the polygon vertices). But I haven't got the "digging in" algo which is proven to minimize the polygon area.

As a side question, is this an NP-complete problem?