THE SOLUTION ON EUCLIDEAN SPACE SHORTEST PATH AND MINIMUM
SPANNING TREE WITH OBSTACLES
L. Xia, P. Hu
xialanfang1@sina.com
MST Problem may be solved with the Delaunay triangulation. every geometric minimal spanning tree of a set of points must be a subgraph of every Delaunay triangulation of that set of points. MST can be obtained by removing the longest edge of each triangulation in the Delaunay triangulation.Two points that are not connected in one Delaunay triangulation of a set of points can never be connected in any minimal spanning tree of that set of points.
If each arc has associated with it a "cost", then the cost of a
spanning tree is the sum of the costs of its arcs. So each spanning
tree has a cost. The smallest of the costs of the spanning trees of a graph is the graph's minimal spanning-tree cost. A minimal spanning tree of the graph is a graph whose cost is the minimal spanning-tree cost. (There
may be more than one minimal spanning tree for a given graph, if there
are multiple spanning trees with the same cost.)
The minimal spanning tree of a set of points is the minimal spanning
tree of the complete graph of those points, that is, the graph in which
there is one arc connecting each pair of nodes. This graph contains
n(n-1)/2 edges, where n is the number of nodes.
A Delaunay triangulation of a set of points is a set of lines connecting points whose Voronoi diagrams share an edge; it is the dual
of the Voronoi diagram, which means it has one face for each
intersection in the Voronoi diagram and one intersection for every face
in the Voronoi diagram, and those faces and intersections are connected
in the same way as their corresponding members in the Voronoi diagram.
The Voronoi diagram of a set of points S is a set of regions R, one per
point; the Voronoi region of each point is the set of points that are
closer to that point than to any other point in S.
So This dissertation mainly aims at MST. Synchronously,it can obstain the shortest path of each point,which is also the basic issue in network analysis.The steps of this solution will be described later.
This paper introduces minimum spanning tree and its usual algorithms, analyzes disadvantages of vector MST algorithm compared with raster algorithm,and introduces map algebra distance transformation and the generation algorithm of Voronoi diagram and Delaunay triangulation based on map algebra,and provides a MST algorithm based on map algebra distance transformation. Considering the fact that MST is a subset of Delaunay triangulation, it can be obtained by removing the longest edge of each triangle in the Delaunay triangulation. This method can be used in Euclidean space with obstacle or without obstacle, which resolves the MST building problem in space with obstacles, especially with arbitrary obstacles, and has some theoretical significance.