I'm trying to minimize the area of a simple (non-intersecting, without holes) polygon by adding points to it, or modifying points of its subset. Let me describe this more formally:
Let:
- $P$ be a polygon consisting of points $\{x_1,x_2,...x_n,x_1\}$
- $S$ be a subset of $P$, bounded by points $x_j$ and $x_k$:
- $m$ be a number of extra points we can allocate
Then, we want to minimize the area of $P$, using the following means:
- modifying the position of points $\{x_{j+1},...,x_{k-1}\}$
- adding new points to the interval $(x_j,x_k)$
Here is a very example for $m =1$ (notice that the boundary points $x_j$ and $x_k$ aren't subject to being modified)
So far, the best I can do is a bruteforce solution. Basically try moving the point around in some discrete increments into various directions, then check if it makes sense (see that it does not create intersections within the polygon), and calculate the area. After that, I check which direction gave the best area, and I continue the process again until the area converges.
Obviously this is a flawed solution in that:
It does not guarantee anything, it is just trial and error
It is extremely computationally expensive
It gives rise to certain anomalies
My question is, could there possibly be a better approach, maybe even one that would guarantee an exact solution in polynomial time?