Shortest-path graph

In mathematics and geographic information science, a shortest-path graph 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.[1]

The shortest-path graph with t=2

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.[1]

References

de Berg, Mark; Meulemans, Wouter; Speckmann, Bettina (2011). "Delineating imprecise regions via shortest-path graphs". Proceedings of the 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems - GIS '11. Vol. 19. pp. 271–280. doi:10.1145/2093973.2094010. ISBN 9781450310314. S2CID 2359926. Retrieved 2 September 2019.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[spg2011-1] Berg, Mark; Meulemans, Wouter; Speckmann, Bettina (2011). "Delineating imprecise regions via shortest-path graphs". Proceedings of the 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems - GIS '11. Vol. 19. pp. 271–280. doi:10.1145/2093973.2094010. ISBN 9781450310314. S2CID 2359926. Retrieved 2 September 2019.