---
abstract: |
    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,\ldots,\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$. Our bound refines the worst-case upper and lower bounds on the worst-case combinatorial complexity of $CH_d(\Sigma)$ for all odd $d\ge{}3$.

    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,\ldots,\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$. This bound is an improvement over the worst-case bound on the combinatorial complexity of the convex hull of a point set where we impose no restriction on the points’ configuration; using the lower bound construction for the sphere convex hull problem, it is also shown to be tight for all odd $d\ge{}3$.

    Finally: (1) we briefly discuss how to compute convex hulls of spheres with a fixed number of distinct radii, or convex hulls of a fixed number of polytopes lying on parallel hyperplanes; (2) 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$; and (3) we state some open problems and directions for future work.

    *Keywords:* high-dimensional geometry,discrete geometry, combinatorial geometry,combinatorial complexity, convex hull,Minkowski sum,spheres,convex polytopes,parallel hyperplanes

    *2010 MSC:* 68U05 (Primary), 52B05, 52B11, 52C45 (Secondary)
author:
- |
    Menelaos I. Karavelas$^{\dagger,\ddagger}$ Eleni Tzanaki$^{\dagger,\ddagger}$\
    *$^\dagger$Department of Applied Mathematics,\
    *University of Crete\
    *GR-714 09 Heraklion, Greece\
    [`{mkaravel,etzanaki}@tem.uoc.gr`]{}\
    *$^\ddagger$Institute of Applied and Computational Mathematics,\
    *Foundation for Research and Technology - Hellas,\
    *P.O. Box 1385, GR-711 10 Heraklion, Greece******
bibliography:
- 'chsch.bib'
title: Convex hulls of spheres and convex hulls of convex polytopes lying on parallel hyperplanes
---

Acknowledgments {#acknowledgments .unnumbered}
===============

Partially supported by the FP7-REGPOT-2009-1 project “Archimedes Center for Modeling, Analysis and Computation”.
