Output-sensitive construction of the union of triangles
Eti Ezra, Micha Sharir · 2004
Abstract. 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 ξ ≪ n triangles, such that � Δ∈S Δ=�Δ∈T Δ, construct efficiently the union of the triangles in T. We show that this problem can be solved in randomized expected time O(n4/3 log n + nξ log2 n), which is subquadratic for ξ = o(n / log2 n). In our solution, we use a variant of the method of Brönnimann and Goodrich [Discrete Comput. Geom., 14 (1995), pp. 463–479] for finding a set cover in a set system of finite VC-dimension. We present a detailed implementation of this variant, which makes it run within the asserted time bound. Our approach is fairly general, and we show that it can be extended to compute efficiently the union of simply shaped bodies of constant description complexity in Rd, when the union is determined by a small subset of the bodies. Key words. union of geometric objects, hitting set, finite VC-dimension, random sampling, set cover, ε-net, output sensitivity