Blindly removing inessential diagonals from a triangulation can lead to a bad convex partitioning

2018-10-17 11:38:25

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 probl