Algorithmic Solutions > LEDA > LEDA Guide > Geometry Algorithms > Euclidean Minimum Spanning Trees

Euclidean Minimum Spanning Trees

The Euclidean minimum spanning tree of a point set L is a tree of minimum cost connecting all points in L, where the cost of an edge is its Euclidean length. The Euclidean minimum spanning tree is a subgraph of the Delaunay diagram of L.

A Euclidean minimum spanning tree for a set of points L is computed as follows

  1. Construct the Delaunay diagram G of L.
  2. Run minimum spanning tree algorithm on G.
  3. Delete all edges from G that do not belong to the minimum spanning tree.


The following program generates a list L of 25 rat_points in the square (-100,-100,100,100) and computes a Euclidean minimum spanning tree for L represented by the parametrized graph G.

On the right you see a screenshot of the program. Clicking on the picture shows the window in original size.

Example of Euclidean MST
#include <LEDA/core/list.h>
#include <LEDA/geo/rat_point.h>
#include <LEDA/geo/random_rat_point.h>
#include <LEDA/graphics/window.h>
#include <LEDA/geo/geo_alg.h>

using namespace leda;

int main()
  list<rat_point> L;

  GRAPH<rat_point,int> G;

  window W;
  W.init(-110,110,-110);; W.display();

  rat_point p;  //draw points in L
  forall(p,L) {W.draw_filled_node(p.to_point(),black);}
  edge e;
  forall_edges(e,G) { //MST
	  point p=G[G.source(e)].to_point();
	  point q=G[].to_point();


  return 0;

See also:

Data Types for 2-D Geometry

Delaunay Diagrams

Minimum Spanning Trees

Windows and Panels

Linear Lists

Parametrized Graphs

Geometry Algorithms




Manual Entries

Manual Page of Geometry Algorithms

Please send any suggestions, comments or questions to
© Copyright 2001-2003, Algorithmic Solutions Software GmbH