mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...

and

geographic information science Geographic information science or geographical information science (GIScience or GISc) is the scientific discipline that studies geographic information, including how it represents phenomena in the real world, how it represents the way humans unders ...

, a shortest-path graph is an undirected graph defined from a set of points in the

Euclidean plane In mathematics, the Euclidean plane is a Euclidean space of dimension two. That is, a geometric setting in which two real quantities are required to determine the position of each point ( element of the plane), which includes affine notions of ...

. 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. The graph is a subgraph of the point set's Gabriel graph and therefore also a subgraph of its Delaunay triangulation.

References

{{reflist Geometric graphs