1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.