Loading...
Please wait, while we are loading the content...
Similar Documents
Geodesic Spanners on Polyhedral Surfaces
| Content Provider | CiteSeerX |
|---|---|
| Author | Kapoor, Sanjiv Li, Xiang-Yang |
| Abstract | Abstract. In this paper we consider the problem of efficiently constructing geodesic t-spanners. We consider finding spanners on the surface of a 3 dimensional poly-hedron. If Steiner vertices are allowed on the surface of the polyhedron, then we are able to construct sparse t-spanners. If no Steiner vertices are allowed, then we establish lower bounds on the maximum node degree, depending on the spanning ratio t and also the total number of vertices of the polyhedron surface. We also consider the case of the surface of a convex polytope P with V vertices. Using its vertex set P and Steiner points, we can construct a t-spanner with a constant de-gree and weight O(MST (U)), where MST (U) is the minimum spanning tree on the set U of vertices on convex polytope. 1 |
| File Format | |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
