Assume that a simple polygon $P$ and a triangulation of it only using the diagonals is given. We say a diagonal $d$ is essential for vertex $v$ if removing $d$ creates a piece that is nonconvex at $v$.
Hertel and Mehlhorn proposed an algorithm for partitioning a polygon to convex pieces. The algorithm says: Start with a triangulation of $P$ (which uses only diagonals). Remove an inessential diagonal; Repeat.
As you see, this algorithm blindly selects an inessential diagonal and is not so intelligent. It is proved that the algorithm is never worse than 4-times optimal in the number of convex pieces.
Now, the question is:
Is there any hope of improving the optimality constant of this algorithm below 4? Suppose the choice of diagonals were made more intelligently. Is a constant of, say, 3 possible?
Note: First I thought of choosing any combination of diagonals and see which of them results in better removal and a better number of convex pieces. But the problem is that this takes a lot of time and also it doesn't give us any kind of constant. Another bug of the H-M algorithm seems to be that it only removes the diagonals when this removal does not result in a nonconvex piece. But if it considers drawing another diagonal, that nonconvex piece may be decomposed to some convex pieces. But all of this does not help in reaching the desired result.