Background: I am implementing triangle mesh CSG using symbolically perturbed exact arithmetic. One of the required subalgorithms is retriangulating a triangular face $T_0$ of the input mesh cut by some number of edges defined by intersections between other faces $T_i$. This reduces to a constrained triangulation problem in the plane. However, I would like to minimize the degree of the predicates involved, and ideally use only triangle orientation tests where only of the triangle edges is a constraint edge (this has the lowest possible degree when mapped up into 3D).
Concretely, my plane triangulation problem is the following: I have an outer triangle $T$ in the plane, and $n$ constraint segments $S_i$ inside $T$. The segments may intersect in their interiors; let $m \ge n$ be the number of vertices including the intersection vertices. I am seeking an $O(m \log m)$ algorithm.
Candidate algorithm: Generate a BSP tree by picking a random input segment $S_i$, dividing the remaining input segments into left and right sets (which will overlap whenever another segment $S_j$ crosses line $S_i$), and recursing. Triangulate the resulting convex polygons arbitrarily, then incrementally remove all unnecessary points generated by the algorithm (those where segments $S_j$ crosses line $S_i$ but not segment $S_i$).
Question: Has this algorithm or a variant been studied previously? Is it $O(m \log m)$ time worst case? Note that the final removal step is not obviously linear time even if only $O(m)$ unnecessary points are generated, so the algorithm could easily be much slower.
