Convex hulls of spheres and convex hulls of convex polytopes lying on parallel hyperplanes

preprint2011arXivOpen access

Abstract

Given a set ΣΣ of spheres in Ed\mathbb{E}^d, with d≥3d\ge{}3 and dd odd, having a fixed number of mm distinct radii ρ1,ρ2,...,ρmρ_1,ρ_2,...,ρ_m, we show that the worst-case combinatorial complexity of the convex hull CHd(Σ)CH_d(Σ) of ΣΣ is Θ(∑1≤i≠j≤mninj⌊d2⌋)Θ(\sum_{1\le{}i\ne{}j\le{}m}n_in_j^{\lfloor\frac{d}{2}\rfloor}), where nin_i is the number of spheres in ΣΣ with radius ρiρ_i. To prove the lower bound, we construct a set of Θ(n1+n2)Θ(n_1+n_2) spheres in Ed\mathbb{E}^d, with d≥3d\ge{}3 odd, where nin_i spheres have radius ρiρ_i, i=1,2i=1,2, and ρ2≠ρ1ρ_2\neρ_1, such that their convex hull has combinatorial complexity Ω(n1n2⌊d2⌋+n2n1⌊d2⌋)Ω(n_1n_2^{\lfloor\frac{d}{2}\rfloor}+n_2n_1^{\lfloor\frac{d}{2}\rfloor}). Our construction is then generalized to the case where the spheres have m≥3m\ge{}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 mm dd-dimensional convex polytopes lying on mm parallel hyperplanes in Ed+1\mathbb{E}^{d+1}, where d≥3d\ge{}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 {P1,P2,...,Pm}\{\mathcal{P}_1,\mathcal{P}_2,...,\mathcal{P}_m\} of mm dd-dimensional convex polytopes lying on mm parallel hyperplanes of Ed+1\mathbb{E}^{d+1} is O(∑1≤i≠j≤mninj⌊d2⌋)O(\sum_{1\le{}i\ne{}j\le{}m}n_in_j^{\lfloor\frac{d}{2}\rfloor}), where nin_i is the number of vertices of Pi\mathcal{P}_i. We end with algorithmic considerations, and we show how our tight bounds for the parallel polytope convex hull problem, yield tight bounds on the combinatorial complexity of the Minkowski sum of two convex polytopes in Ed\mathbb{E}^d.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.