Convex hulls of spheres and convex hulls of disjoint convex polytopes

Given a set Σ   of spheres in EdEd, with d⩾3d⩾3 and d odd, having a constant number of m   distinct radii ρ1,ρ2,…,ρmρ1,ρ2,…,ρm, we show that the worst-case combinatorial complexity of the convex hull of Σ   is Θ(∑1⩽i≠j⩽mninj⌊d2⌋), where nini is the number of spheres in Σ   with radius ρiρi.To prove the lower bound, we construct a set of Θ(n1+n2)Θ(n1+n2) spheres in EdEd, with d⩾3d⩾3 odd, where nini spheres have radius ρiρi, i=1,2i=1,2, and ρ2≠ρ1ρ2≠ρ1, such that their convex hull has combinatorial complexity Ω(n1n2⌊d2⌋+n2n1⌊d2⌋). Our construction is then generalized to the case where the spheres have m⩾3m⩾3 distinct radii.For the upper bound, we reduce the sphere convex hull problem to the problem of computing the worst-case combinatorial complexity of the convex hull of a set of m disjoint d  -dimensional convex polytopes in Ed+1Ed+1, where d⩾3d⩾3 odd, a problem which is of independent interest. More precisely, we show that the worst-case combinatorial complexity of the convex hull of a set of m disjoint d  -dimensional convex polytopes in Ed+1Ed+1 is O(∑1⩽i≠j⩽mninj⌊d2⌋), where nini is the number of vertices of the i  -th polytope. Using the lower bound construction for the sphere convex hull problem, it is also shown to be tight for all odd d⩾3d⩾3.Finally, we discuss how to compute convex hulls of spheres with a constant number of distinct radii, or convex hulls of a constant number of disjoint convex polytopes.