The complexity of the union of (α, β)-covered objects
Alon Efrat · 1999
An (α, β)-covered object is a simply connected planar region c with the property that for each point p ∈ ∂c there exists a triangle contained in c and having p as a vertex, such that all its angles are at least α and all its edges are at least β ·diam(c)-long. This notion extends that of fat convex objects. We show that the com-binatorial complexity of the union of n (α, β)-covered objects of ‘constant description com-plexity ’ is O(λs+2(n) log 2 n log logn), where s is the maximum number of intersections between the boundaries of any pair of the given objects. 1