On the Non-Locality of Edge Insertions
Florestan Brunck · arXiv (Cornell University) · 2023
We challenge the idea that edge insertions are local improvement operations and show that the edge-insertion algorithm must sometimes insert an edge between vertices that are at the farthest combinatorial distance apart, and that this edge must also cross linearly many edges of the triangulation for the algorithm to escape a local optimum and return the optimal triangulation.