Convex hull or two convex hulls of the given set of points with the lowest possible perimeter

Question

Given n>=3 points on the plane. We are looking for one or two polygons that fulfill these conditions:

1. Every point from the given set of points is located in the polygon or at the perimeter of at least one of those polygons .
2. Every vertex of every polygon is in one of the given points .
3. The polygon can't have zero area.

Calculate the lowest possible value of the total perimeter of the found polygons.

I don't have a problem with finding a polygon with the lowest perimeter but I can't find any effective solution to find two polygons with the lowest perimeter. (for n>=300)

I need some hint or something, what could help me to figure out how to solve it.

Answer 1

First step is to calculate the convex hull. Assume your points on the convex hull H are p0, p1, p2, p3, ... , pn, p0. Let us assume that the optimal convext hulls A and B contain subsets pA and pB from this list. Then pA and pB are obtained by splitting H at two points.

Now you can see that you can splits points on H only O(n^2) ways.

Since you do not want complete answer, I am leaving rest to you.