If holes are ignored (only the outline is computed), this is an instance of computing a single face of arrangement of half-lines (rays).

With half-lines, the maximum number of vertices in a single face is $\Theta(n)$. Therefore, this problem can be solved in $\Theta(n \log n)$ expected time using the randomized divide-and-conquer approach. See [1] chap.6.2 for details.

If holes are allowed, the number of vertices is $\Theta(n^2)$ in the worst case. Consider the $n \times n$ grid rotated by 45 degrees. Then, replace each line segment with a very acute triangle.

• [1] P. K. Agarwal and M. Sharir. Davenport-Schinzel sequences and their geometric applications, 2015.