Shortest-path graph

Shortest-path graph

In mathematics and geographic information science, a Shortest-path graph (also known as a SPG(t)) is an undirected graph defined from a set of points in the Euclidean plane. The Shortest-path graph is proposed with the idea of inferring edges between a point set such that the shortest path taken over the inferred edges will roughly align with the shortest path taken over the imprecise region represented by the point set. The edge set of the Shortest-path graph varies based on a single parameter t ≥ 1. When the weight of an edge is defined as its Euclidean length raised to the power of the parameter t ≥ 1, the edge is present in the Shortest-path graph if and only if it is the least weight path between its endpoints.

Properties of Shortest-path graph

When the configuration parameter t goes to infinity, Shortest-path graph become the minimum spanning tree of the point set. Also it is a subgraph of Gabriel graph. Therefore also a subgraph of Delaunay triangulation.

Algorithms

To extract the shortest path graph of a point set, first we need to created the complete graph of the Delaunay triangulation of the point set. Then, each edge is evaluated against the euclidean shortest path, both raised to the power of the value of t. If the resulting value for the path is larger than euclidean shortest path, then the direct edge is removed.

Applications

Shortest-path graph has been applied in the study of identifying the boundary of a region given as a point set, and for visualizing overlapping point sets.