Output-Sensitive Construction of the Union of Triangles

We present an efficient algorithm for the following problem: Given a collection T = {Δ1,Δn} of n triangles in the plane, such that there exists a subset S ⊂ T (unknown to us), of ∪Δ ∈ S Δ = ∪ΔΔ∈TΔ n triangles, such that ζ « construct efficiently the union of the triangles in T. We show that this problem can be solved in subquadratic time. In our solution, we use the approximate Disjoint-Cover (DC) algorithm, presented as a heuristics in [9]. We present a detailed implementation of this method, which combines a variety of techniques related to range-searching in two dimensions. We provide a rigorous analysis of its performance in the above setting, showing that it does indeed run in subquadratic time (for a reasonable range of ζ).