CODEWITHSUNDEEP
algorithmgeometrycomputational-geometryconvex-hull
Serillan
Serillan

Reputation: 227

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


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.

Upvotes: 2

Views: 589

Answers (1)

ElKamina
ElKamina

Reputation: 7807

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.

Upvotes: 2

Related Questions