On compatible triangulations with a minimum number of Steiner points (Q2192383)

Compatible triangulations are used in computer graphics, e.g. in morphing. Two vertex-labelled polygons are compatible if they have the same clockwise cyclic ordering of vertices. This definition can be extended to polygonal regions and to triangulations. It is known that every pair of compatible \(n\)-vertex polygonal regions can be extended to compatible triangulations by adding the Steiner points. An intriguing open question is to decide if two compatible polygons have compatible triangulations with at most \(k\) Steiner points. In this paper it is proven that this problem is NP-hard for polygons with holes. For the other polygons this question still remains open.