There is a convex geo polygon consisting of 200 vertexes (lat, lng). Lets call it M. There is a set of geo points inside it (about 15 000 points). P = {1 ... 15 000}. Also there is another convex geo polygon inside the first one (M) and consisting of 50 vertexes. Lets call it S. Polygon S contains 43 percent of points of P. I need some algorithm to increase the area of S (by moving the points of original polygon S) to get minimum area that will contain 55 percent of points of P. Is it possible?
It is not always possible if the modified S (lets call it S') needs to be 100% within M.
Here the example:
Let M be kind of a circle where 43% of the points are near the center and all 57% other points on the rim of the circle. Let S be a triangle with the corners on the rim of the circle.
There is no way to get more of the points on the rim of the circle within the triangle with just moving the corners of the triangle within M because only maximal 3 of the points on the rim of the circle can be part of the triangle. So you cannot achieve the 55% in S' as long as it has to remain a triangle and the corners need to be inside M.