THE SOLUTION ON EUCLIDEAN SPACE SHORTEST PATH AND MINIMUM SPANNING TREE WITH OBSTACLES

L. Xia, P. Hu

School of Resource and Environment Science, Wuhan university, Wuhan, China

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.