Trivial. At least if the triangles are not allowed to cross that internal boundary.
Simply create a polygon that describes the boundary, as a list of edges. Include those points in the set of points for your triangulation.
Set that list of edges from the polygon as constrained edges, and form a constrained triangulation.
No triangle will be able to CROSS one of those edges now, although there will be triangles INSIDE that constrained region. Now just delete any triangle from the tessellation that has all three vertices on the constraint polygon. What remains will have edges on the polygon, but none that can cross it.
You will not be able to insist that nothing even touch that region using constraints, while allowing edges to otherwise come arbitrarily close. The best you can do is to create a polygon as I suggested, but first move each vertex slightly outside. Thus, you must create a polygon that entirely contains your constraint domain yet lies some finite distance outside of the constraint region, then use the scheme I suggested above.
