On compatible triangulations with a minimum number of Steiner points (Q2192383)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On compatible triangulations with a minimum number of Steiner points |
scientific article |
Statements
On compatible triangulations with a minimum number of Steiner points (English)
0 references
17 August 2020
0 references
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.
0 references
polygonal regions
0 references
compatible triangulations
0 references
NP-hardness
0 references
linear homeomorphisms
0 references