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

DOI10.1145/1998196.1998262MaRDI QIDQ5404454zbMATH OpenOpenAlexFDO

Authors Menelaos I. Karavelas, Eleni Tzanaki

Publication date 24 March 2014

Published in Proceedings of the twenty-seventh annual symposium on Computational geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0911.5086

zbMATH Keywords

discrete geometryconvex hullhigh-dimensional geometrycombinatorial geometryconvex polytopesspherescombinatorial complexityparallel hyperplanesminkowski sum

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Combinatorial complexity of geometric structures (52C45)

Abstract: Given a set $Sigma$ of spheres in $mathbb{E}^d$, with $dge3$ and $d$ odd, having a fixed number of $m$ distinct radii $h{o}_1,h{o}_2,\mathrm{...},h{o}_m$, we show that the worst-case combinatorial complexity of the convex hull $C{H}_d(Sigma)$ of $Sigma$ is $Theta(su{m}_{1leiejlem}{n}_i{n}_j^{lfloorfracd2floor})$, where $n_i$ is the number of spheres in $Sigma$ with radius $h{o}_i$. To prove the lower bound, we construct a set of $Theta(n_1+n_2)$ spheres in $mathbb{E}^d$, with $dge3$ odd, where $n_i$ spheres have radius $h{o}_i$, $i=1,2$, and $h{o}_{2}eh{o}_1$, such that their convex hull has combinatorial complexity $Omega(n_1{n}_2^{lfloorfracd2floor}+n_2{n}_1^{lfloorfracd2floor})$. Our construction is then generalized to the case where the spheres have $mge3$ 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 $dge3$ 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,\mathrm{...},mathcal{P}_m$ of $m$ $d$-dimensional convex polytopes lying on $m$ parallel hyperplanes of $mathbb{E}^{d+1}$ is $O(su{m}_{1leiejlem}{n}_i{n}_j^{lfloorfracd2floor})$, 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$.

Recommendations

• Convex hulls of spheres and convex hulls of disjoint convex polytopes
• An algorithm for constructing the convex hull of a set of spheres in dimension \(d\)
• scientific article; zbMATH DE number 2079353
• The convex hull of random balls
• New Lower Bounds for Convex Hull Problems in Odd Dimensions

Cited in

(7)

• Real zeros of mixed random fewnomial systems
• Convex hulls of \(f\)- and \(\beta\)-vectors
• Equiaffine inner parallel curves of a plane convex body and the convex hulls of randomly chosen points
• Convex hulls of spheres and convex hulls of disjoint convex polytopes
• Minimal surface convex hulls of spheres
• scientific article; zbMATH DE number 2079353 (Why is no real title available?)
• Convex hulls of spatial polygons with a fixed convex projection

This page was built for publication: Convex hulls of spheres and convex hulls of convex polytopes lying on parallel hyperplanes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5404454)