Flip distance between two triangulations of a point set is NP-complete (Q906837): Difference between revisions

Given a triangulation in the plane, a flip operates on two triangles that share an edge and form a convex quadrilateral. The authors investigate the complexity of computing the flip distance, that is, the minimum number of flips to transform one triangulation to another see [\textit{P. Bose} and \textit{F. Hurtado}, ibid. 42, No. 1, 60--80 (2009; Zbl 1146.05016)]. The main result of the authors is that it is NP-complete to compute the flip distance between two triangulations of a polygon with holes, or of a set of points in the plane. It is observed that after submission of their paper, the authors learnt that \textit{A. Pilz} [ibid. 47, No. 5, 589--604 (2014; Zbl 1293.65032)] independently proved the same result and then strengthened it to prove APX-hardness.