Flip distance between triangulations of a planar point set is APX-hard (Q2444311): Difference between revisions

The author considers the problem of the flip distance between two triangulations \(T_1\), \(T_2\) of a given point set in the Euclidean plane, i.e., the minimization of the number of edge flips to the transform from \(T_1\) to \(T_2\). He proves that the problem is APX-hard. To show this he takes the minimum vertex cover (i.e., given a simple graph with \(n\) vertices choose a subset \(C\) of the set of vertices such that every edge has at least one vertex in \(C\) and \(|C|\) is minimized) and makes the AP-reduction of this problem to the flip distance problem. Because it is known that the minimum vertex cover is APX-hard so the flip distance problem is also APX-hard. In the construction of the AP-reduction and its analysis the author uses double chains and geometric gadgets.