Find the maximum convex area My question is very similar to Plow's Question; but with this difference:
How can I find the maximum convex area that can fit inside a non-convex region?
For an example, consider this non-convex region :

Any ideas or solution would be appreciated, thanks.
 A: This answer deals only with the simple case, without holes or self-intersections.
Take the bounday, and identify elements which are not locally convex. I call a point on the boundary locally convex if there exists a disk of radius $\epsilon$ around the point which, when intersected with the shape, will yield a convex intersection. In the case of polygons, the non-convex boundary elements will be the vertices with interior angle exceeding $\pi$. In the case of a smooth curve, the non-convex boundary elements will be those parts of the curve where the curvature bends inwards, with two inflection points as the end points of the non-convex element.
For each such non-convex element you have to find one line which is tangent to the boundary element in question. That line defines a half plane pointing inwards from the boundary. The intersection of all these half planes with the original shape will be a convex shape.
So now your task is that of finding suitable lines. You can split that task in two parts. In a combinatoric step, you can investigate which combinatorics could possibly occur. Basically you check which lines might intersect within the shape, and which outside, and you iterate over all possible combinations that can occur this way. In the next step, you try to optimize the area for a given combinatorics, using non-linear optimization. I'm not sure whether determining the combinatorics up front will be enough to make this optimization problem convex, but I expect this to be the case for many practical applications at least.
To illustrate my ideas, here is the result when applied to your example shape:

This was done using a polygonal approximation of your shape with 269 vertices. I didn't implement the combinatorics preprocessing, but instead tried all possible line combinations in a rather brute-force approach. Basically I had four nested loops, one for each non-convex boundary element (drawn in red). For each I took all possible combinations of two consecutive polygonal vertices to define a line, and in the innermost loop I computed the resulting area. The blue lines were the optimal solution, resulting in the green convex shape.
I wrote a bit more on this implementation in my answer to the corresponding Stack Overflow question.
