The Complexity of the Union of $(\alpha,\beta)$-Covered Objects
Alon Efrat · SIAM Journal on Computing · 2005
An $(\alpha,\beta)$-covered object is a simply connected planar region c with the property that for each point $p\in\partial c$ there exists a triangle contained in c and having p as a vertex, such that all its angles are at least $\alpha>0$ and all its edges are at least $\beta\cdot{\rm \diam}(c)$-long. This notion extends that of fat convex objects. We show that the combinatorial complexity of the union of n $(\alpha,\beta)$-covered objects of "constant description complexity" is $O(\lambda_{s+2}(n) \log^2n\log\log n)$, where s is the maximum number of intersections between the boundaries of any pair of given objects, and $\lambda_s(n)$ denotes the maximum length of an $(n,s)$-Davenport--Schinzel sequence. Our result extends and improves previous results concerning convex $\alpha$-fat objects.