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

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

2009-11-26

arxiv.org/abs/0911.5086v5

Computer Science

Computational Geometry

22 pages, 5 figures, new proof of upper bound for the complexity of the convex hull of parallel polytopes (the new proof gives

Scientific paper

Given a set $\Sigma$ of spheres in $\mathbb{E}^d$, with $d\ge{}3$ and $d$ odd, having a fixed number of $m$ distinct radii $\rho_1,\rho_2,...,\rho_m$, we show that the worst-case combinatorial complexity of the convex hull $CH_d(\Sigma)$ of $\Sigma$ is $\Theta(\sum_{1\le{}i\ne{}j\le{}m}n_in_j^{\lfloor\frac{d}{2}\rfloor})$, where $n_i$ is the number of spheres in $\Sigma$ with radius $\rho_i$. To prove the lower bound, we construct a set of $\Theta(n_1+n_2)$ spheres in $\mathbb{E}^d$, with $d\ge{}3$ odd, where $n_i$ spheres have radius $\rho_i$, $i=1,2$, and $\rho_2\ne\rho_1$, such that their convex hull has combinatorial complexity $\Omega(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\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 $m$ $d$-dimensional convex polytopes lying on $m$ parallel hyperplanes in $\mathbb{E}^{d+1}$, where $d\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 $\{\mathcal{P}_1,\mathcal{P}_2,...,\mathcal{P}_m\}$ of $m$ $d$-dimensional convex polytopes lying on $m$ parallel hyperplanes of $\mathbb{E}^{d+1}$ is $O(\sum_{1\le{}i\ne{}j\le{}m}n_in_j^{\lfloor\frac{d}{2}\rfloor})$, where $n_i$ is the number of vertices of $\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 $\mathbb{E}^d$.

Affiliated with

Also associated with

No associations

Rating

Convex hulls of spheres and convex hulls of convex polytopes lying on parallel hyperplanes does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Convex hulls of spheres and convex hulls of convex polytopes lying on parallel hyperplanes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Convex hulls of spheres and convex hulls of convex polytopes lying on parallel hyperplanes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-194726