Convex hulls of spheres and convex hulls of convex polytopes lying on parallel hyperplanes
Menelaos I. Karavelas, Eleni Tzanaki · 2011
Given a set Σ of spheres in Ed, with d≥3 and d odd, having a fixed number of m distinct radii ρ1,ρ2,...,ρm, we show that the worst-case combinatorial complexity of the convex hull CHd(Σ) of Σ is Θ(Σ{1≤i≠j≤m}ninj⌊ d/2 ⌋), where ni is the number of spheres in Σ with radius ρi. Our bound refines the worst-case upper and lower bounds on the worst-case combinatorial complexity of CHd(Σ) for all odd d≥3.