(Weakly) Self-approaching geometric graphs and spanners

摘要

A geometric graph is called self-approaching, if for each (ordered) pair of vertices of the graph, there exists a self-approaching (directed) path between them. A path from a vertex u to a vertex v of the graph is called self-approaching, if for any point (not-just vertex) x on the path, the distance between x and any point that starts at u and moves toward x is decreasing. A path is called an increasing-chord, if it is self-approaching from both sides, source to destination and destination to source. A geometric graph is called a self approaching t-spanner, for t 1, if for each pair (u, v) of vertices of the graph, there exists a self-approaching path from u to v of length at most t times the Euclidean distance between u and v.