Minimizing the area of a simple polygon by modifying/adding to a subset of its vertices

Question

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?

Answer 1

Try all possibilities for vertices $P,Q,R,S$ where $P,Q$ are adjacent and $R,S$ are adjacent (there are $O(n^2)$ possibilities). For each such possibility, find the best way to add a point $T$ after $P$ and before $Q$, such that $T$ falls on the line segment $RS$. This involves finding a point $T$ on the line segment $RS$ that maximizes the area of the triangle $PTQ$. You should be able to do that in $O(1)$ time. Repeat for each possible $P,Q,R,S$ and take the best one found. This should yield an $O(n^2)$ time algorithm.

I don't know if it is possible to do better than $O(n^2)$ time.