Given n>=3 points on the plane.
We are looking for one or two polygons that fulfill these conditions:
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.
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.