| Autor: |
Michiel Smid, Prosenjit Bose, Paz Carmi, Mirela Damian, Jean-Lou De Carufel, Darryl Hill, Anil Maheshwari, Yuyang Liu |
| Jazyk: |
angličtina |
| Rok vydání: |
2016 |
| Předmět: |
|
| Zdroj: |
Journal of Computational Geometry, Vol 7, Iss 1 (2016) |
| Druh dokumentu: |
article |
| ISSN: |
1920-180X |
| DOI: |
10.20382/jocg.v7i1a19 |
| Popis: |
Let $P$ be a convex polyhedron in $\mathbb{R}^3$. The skeleton of $P$ is the graph whose vertices and edges are the vertices and edges of $P$, respectively. We prove that, if these vertices are on the unit-sphere, the skeleton is a $(0.999 \cdot \pi)$-spanner. If the vertices are very close to this sphere, then the skeleton is not necessarily a spanner. For the case when the boundary of $P$ is between two concentric spheres of radii $1$ and $R>1$, and the angles in all faces are at least $\theta$, we prove that the skeleton is a $t$-spanner, where $t$ depends only on $R$ and $\theta$. One of the ingredients in the proof is a tight upper bound on the geometric dilation of a convex cycle that is contained in an annulus. |
| Databáze: |
Directory of Open Access Journals |
| Externí odkaz: |
|
