On the Non-Locality of Edge Insertions

A nice observation which shows that problems optimised by the edge insertion and not by flipping algorithm can be very different. For the max-min angle triangulation, the well-known Delaunay triangulation can be obtained by flips, as in their case some Euclidean geometry magic shows that flips always yield a strict local improvement. For the min-max angle problem - which one might expect to be very similar as it is indeed intimitately related - we show that there is no such local improvement and the edge insertion algorithm must sometimes connect vertices that are as far apart as can be and cross linearly many edges of the triangulation.