Skip to main content
15 of 16
correcting error in the example section
Thirlan
  • 157
  • 5

Polygon within polygon generalization problem

I would like to apologize to all the posts below. Picked the wrong forum to post this in originally. However rather than make this a complete waste I've reworked the question to be a true "Theoretical Computer Science" problem.

Problem: Create an algorithm that takes a set of n ordered points in a 2D plane that form the contour of a simple polygon A that may or may not be concave and creates a new polygon B with m points such that:

  1. all points in A are contained within B
  2. 3 <= m < n
  3. B is the polygon in the set of all Bs with the smallest area
  4. B must be a simple polygon (i.e. no self-intersections).
  5. The input to the algorithm is polygon A and "m".
  6. Coincidence of segments in B with segments in A are allowed.

Some example inputs and expected outputs:

  1. If A is a square and m is 3 then B would be the triangle with the smallest surface area that contains A.
  2. If A is a hexagon and m is 4 then B would be a quadrilateral with the smallest surface area that contains A.

Good luck to everyone who tries this problem out. I can promise you this will be very hard especially now that the solution must be optimal.

Thirlan
  • 157
  • 5