Minimizing the area of a simple polygon by modifying/adding to a subset of its vertices
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.