On the union of κ-round objects
Boris S. Aronov, Alon Efrat, Vladlen Koltun, Micha Sharir · 2004
A compact body c in ℝd is κ-round if for every point p∈ ∂c there exists a closed ball that contains p, is contained in c, and has radius κ diam c. We show that, for any fixed κ>0, the combinatorial complexity of the union of n κ-round, not necessarily convex objects in ℝ3 (resp., in ℝ4) of constant description complexity is O(n2+ε) (resp., O(n3+ε)) for any ε>0, where the constant of proportionality depends on ε, κ, and the algebraic complexity of the objects. The bound is almost tight.