I'm working on a piece of software that deals with several polygons, These polygons have far to many corners and I would like to reduce them such that the total area in the polygons and general shape don't change overly much (within a few percent). There is however one problem and that is that these polygons are not allowed to intersect.
These polygons can also be inside of each other or next to each other. So for example the following polygon 
should not be simplified into
Because now we have an intersection
but something like 
is ok. Do note how it's possible for one polygon to contain another.
This is also something I would (if possible) like to be somewhat efficient with, currently the program is bottlenecked by an O(n^3) calculation somewhat later so any solution that is faster then that is good but anything O(n³) or slower is a no go. Anybody know how to check this efficiently?
You might start by computing the Hausdorff distance between the two polygons. It can easily be done in $O(n^2)$ time where $n$ is the total number of vertices. If the distance is $r$, then changes to both polygons by Hausdorff distances $< r/2$ will be safe.