Spanners for Geodesic Graphs and Visibility Graphs

作者：Abam Mohammad Ali^*

来源：Algorithmica, 2018, 80(2): 515-529.

DOI：10.1007/s00453-016-0268-y

• Spanners
• Geodesic distance
• Visibility graphs
• Polygonal domains

Let be a set of n points inside a polygonal domain . A polygonal domain with h holes (or obstacles) consists of h disjoint polygonal obstacles surrounded by a simple polygon which itself acts as an obstacle. We first study t-spanners for the set with respect to the geodesic distance function where for any two points p and q, is equal to the Euclidean length of the shortest path from p to q that avoids the obstacles interiors. For a case where the polygonal domain is a simple polygon (i.e., ), we construct a ()-spanner that has edges. For a case where there are h holes, our construction gives a ()-spanner with the size of . Moreover, we study t-spanners for the visibility graph of (, for short) with respect to a hole-free polygonal domain . The graph is not necessarily a complete graph or even connected. In this case, we propose an algorithm that constructs a ()-spanner of size for some . In addition, we show that there is a set of n points such that any -spanner of must contain edges.

• 出版日期2018-2