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

DOI10.1145/1998196.1998262zbMATH Open1283.68370arXiv0911.5086OpenAlexW2041247614MaRDI QIDQ5404454FDOQ5404454

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)

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$.

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

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

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)

Cited In (7)

• Real zeros of mixed random fewnomial systems
• Convex hulls of \(f\)- and \(\beta\)-vectors
• Convex hulls of spheres and convex hulls of disjoint convex polytopes
• Equiaffine inner parallel curves of a plane convex body and the convex hulls of randomly chosen points
• Minimal surface convex hulls of spheres
• Title not available (Why is that?)
• 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)