Are there any algorithms related to the following problem that could be usefull for solving it?
I have a convex hull built on some point set. I would like to simplify it (reduce number of points) by still keeping its perimiter (or area) as small as possible. New simplified polygon should not intersect the original hull.
The basic idea I am trying to implement is to calculate for each point of a polygon perimeter added by removal of this point. And then remove the cheapest point (which removal adds minimum value to the perimiter).
So we keep iterating and removing points while added perimiter or area value is suitable and passes some creteria.
Here comes the problem:
When removing point p1 we introduce a new edge formed by previous point p0 and the next point p2. This new edge can be non-optimal or invalid (intersecting the original hull). So I would like to adjust points p0 and p2 along their edges to keep perimeter valid and small as possible.
How can I find these adjusted positions of p0 and p2 ?
I think my current problem is finding the optimal slope of the new (green) edge. But I am looking forward to any related suggestions and algorithms.