<p>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.</p>

CC BY-SA 3.0
2014-05-09T20:31:03.950Z
2014-05-09T20:31:03.950Z
Geoffrey Irving
<p><strong>Background</strong>: 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).</p>

<p>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.</p>

<p><strong>Candidate algorithm</strong>: 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 <em>segment</em> $S_j$ crosses <em>line</em> $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$).</p>

<p><strong>Question</strong>: 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.</p>

<cg.comp-geom><binary-space-partitions>
Is this constrained planar triangulation algorithm $O(m \log m)$?
Geoffrey Irving
# Is this constrained planar triangulation algorithm $O(m \log m)$?

(Asked by: username_0 on 2014-05-09)

**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.

**Tags:** cg.comp-geom, binary-space-partitions


---

## 1 answers

### Answer by username_0 on 2014-05-09. Score: 1

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.


---

