Convex hulls of spheres and convex hulls of disjoint convex polytopes
| Autor: | Raimund Seidel, Eleni Tzanaki, Menelaos I. Karavelas |
|---|---|
| Rok vydání: | 2013 |
| Předmět: |
Convex hull
Convex analysis Control and Optimization Convex set Subderivative Computer Science Applications Combinatorics Computational Mathematics Computational Theory and Mathematics Convex polytope Mathematics::Metric Geometry Convex body Convex combination Geometry and Topology Orthogonal convex hull Mathematics |
| Zdroj: | Computational Geometry. 46:615-630 |
| ISSN: | 0925-7721 |
| DOI: | 10.1016/j.comgeo.2013.02.001 |
| Popis: | Given a set @S of spheres in E^d, with d>=3 and d odd, having a constant number of m distinct radii @r"1,@r"2,...,@r"m, we show that the worst-case combinatorial complexity of the convex hull of @S is @Q(@?"1"= "j"= =3 odd, where n"i spheres have radius @r"i, i=1,2, and @r"2 @r"1, such that their convex hull has combinatorial complexity @W(n"1n"2^@?^d^2^@?+n"2n"1^@?^d^2^@?). Our construction is then generalized to the case where the spheres have m>=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 disjoint d-dimensional convex polytopes in E^d^+^1, where d>=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 of m disjoint d-dimensional convex polytopes in E^d^+^1 is O(@?"1"= "j"= =3. Finally, we discuss how to compute convex hulls of spheres with a constant number of distinct radii, or convex hulls of a constant number of disjoint convex polytopes. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect