Is this constrained planar triangulation algorithm $O(m \log m)$?
Unfortunately, this algorithm is $\Omega(n^2)$ even if no unnecessary vertices are generated.  If the $S_i$ form a convex polygon inside $T$, the BSP tree is degenerate regardless of the order in which segments are inserted.