Geodesic Spanners on Polyhedral Surfaces

摘要

In this paper we consider the problem of efficiently constructing geodesic t-spanners. We consider finding sparse spanners on the surface of a 3 dimensional polyhedron allowing for steiner vertices. If Steiner vertices are not 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 degree and weight O(MST(U)), where MST(U) is the minimum spanning tree on the set U of vertices on convex polytope.