Triangle Covers of Polygons: Approximation Algorithms and Complexity
We study the geometric set cover problems of covering and partitioning a polygon into a minimum number of triangles. While the decision version of the covering problem is known to be APX-hard and $\exists\mathbb R$-complete (even for polygons without holes and vertices in general position), the computational complexity...