Return to Question

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-interestions).
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 square 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.

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.

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-interestions).
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:

• If A is a square and m is 3 then B would be the triangle with the smallest surface area that contains A.
• If A is a hexagon and m is 4 then B would be a square 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.

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-interestions).
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 square 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.