Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1016/j.comgeo.2013.02.001 | Comput. Geom. |
Keywords | Field | DocType |
worst-case combinatorial complexity,convex hull,combinatorial complexity,independent interest,distinct radius,constant number,i sphere,m distinct radius,sphere convex hull problem,disjoint convex polytopes,spheres,combinatorial geometry,discrete geometry | Orthogonal convex hull,Discrete mathematics,Combinatorics,Convex body,Convex combination,Convex set,Convex hull,Subderivative,Convex polytope,Mathematics,Convex analysis | Journal |
Volume | Issue | ISSN |
46 | 6 | 0925-7721 |
Citations | PageRank | References |
1 | 0.36 | 22 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Menelaos I. Karavelas | 1 | 229 | 18.99 |
| Raimund Seidel | 2 | 60 | 6.03 |
| Eleni Tzanaki | 3 | 24 | 6.72 |