Latest update

# 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