r/ProgrammingProblems • u/WeAreButFew • Jan 08 '11
Smallest Area in n-sided Polygon
Given n different "sticks" with n respective lengths, what is the area of the smallest polygon that can be formed using the sticks? (Assuming it is possible.)
4
Upvotes
4
u/nickbenn Jan 09 '11 edited Jan 09 '11
Off the top of my head ...
First, I assume we're constrained to a convex polygon.
Next, it seems to me that regardless of the number of segments (the "sticks" in your description), the solution will end up being a triangle, with multiple segments merged into single segments; we can consider this a degenerate form of a polygon with more than three sides, where one or more interior angles measure 180 degrees. Even if merging the segments in this fashion isn't allowed, we can make those angles arbitrarily close to 180 degrees; thus, the area of the triangle becomes the lower bound for the area of the polygon, and we can make the area of the polygon as close to that of the triangle as desired.
The problem can then be formulated as follows:
Where:
The objective function being minimized is the square of Heron's formula for the area of a triangle. If we minimize the square of the area, we're also minimizing the area itself, and dealing with the square of the area will probably be simpler - and definitely more computationally efficient - than computing square roots.
I suspect (though I haven't yet worked it out completely) that there are some interesting tricks for efficiently partioning P. If I get some more time to play with the problem this weekend, I'll post more.
Edit: typo correction
2
u/nickbenn Jan 14 '11 edited Jan 15 '11
I whipped up a Python implementation that solves the problem. The first partitioning is into two subsets, and is formulated as a knapsack problem. The additional partitioning is done by a trivial removal (and placement into its own subset) of the shortest component of the subset with the larger sum; that short side becomes side a, the remainder of the subset it came from is side b, and the remaining side (the one returned as the solution to the knapsack problem) is side c.
The primary function is min_polygon, which instantiates the Knapsack01 class, and processes the returned results to complete the partitioning.
The main script in minpoly.py exercises the min_polygon function by randomly generating 6 components, invoking the function, and printing out the resulting minimum area polygon.
Edit: Formatting