Any non-convex polygon in the plane can be triangulated in O(n) time with no Steiner points; that is, every vertex of the triangulation is a vertex of the polygon. Moreover, every triangulation has exactly n-2 triangles.
However, determining whether a non-convex polyhedron in R^3 can be triangulated without Steiner points is NP-complete. The NP-hardness result holds even if you are given a triangulation with one Steiner point, so even approximating the minimum number of Steiner points required is NP-hard. [Jim Ruppert and Raimund Seidel. On the Difficulty of Triangulating Three-Dimensional Nonconvex Polyhedra. Discrete Comput. Geom. 1992.]
If the given polyhedron is convex, finding a triangulation is easy, but finding the triangulation with the minimum number of tetrahedra is NP-hard. [Alexander Below, Jesús de Loera, and Jürgen Richter-Gebert. The complexity of finding small triangulations of convex 3-polytopes. J. Algorithms 2004.]