minimal spanning trees and Delaunay triangulations
Kragen Sitaker
kragen@pobox.com
Thu, 8 Jul 1999 16:35:25 -0400 (EDT)
This is probably a well-known result, or maybe it's just wrong, but I
was excited when I discovered it this morning.
It seems that every geometric minimal spanning tree of a set of points
must be a subgraph of every Delaunay triangulation of that set of points.
Background
==========
Delaunay triangulations
-----------------------
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 these regions take the form of polygons bounded by perpendicular
bisectors of the line segments between the points in S, except that
some of them are not polygons because they extend to infinity. But not
all perpendicular bisectors participate; some are too far away. For
example, in this Voronoi diagram, the perpendicular bisector of A and D
does not help to bound the regions of A and D:
\ B /
A >---< D
/ C \
To look at it another way, all of the perpendicular bisector of A and D
is closer to either B or C than to A, and closer to either B or C than
to D.
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.
You will note that if the Voronoi diagram has intersections with more
than three lines intersecting, the Delaunay triangulation will not
consist of triangles:
A | B A---B
--+-- <- Voronoi Diagram Delaunay "triangulation" -> | |
C | D C---D
I don't know what the traditional remedy for this is, but for this
discussion, I will say that you can connect either A to D or C to B to
get a valid Delaunay triangulation. This corresponds to dividing the
degree-4 point in the Voronoi diagram into two degree-3 points in
either of the two possible ways.
So each perpendicular bisector that separates two Voronoi regions
corresponds to a Delaunay link between the points in those regions.
There's another property of Delaunay triangulations, which is commonly
used to define the Delaunay triangulation of a set of points: in the
Delaunay triangulation, the circle circumscribed around any triangle of
the triangulation does not contain any other points in the set. In the
boundary case above of the corners of a rectangle, you will note that
the circle around any three of the points exactly touches the fourth
point.
There are efficient methods to calculate the Delaunay triangulation of
a set of points, O(N lg N) if I remember correctly.
Graphs
------
A graph is a set of vertices, or nodes, V, and a set of lines, or arcs,
A. Each arc is an unordered pair of nodes from V.
Normally we have some information associated with each node, and
sometimes with each arc. For example, each node might have a physical
position in space, an IP address, or a weight; each arc might have a
cost. One particularly interesting case is where each node is
associated with a point in the plane and each arc has a "length" that
is the Euclidean distance between the points of the nodes at its ends.
Two nodes X and Y in a graph are connected if A contains the pair [X,
Y], or if X is connected to a node that is connected to Y.
A graph is "connected" if all pairs of nodes from V are connected.
If we have two graphs (V, A) and (V', A'), the second one is a subgraph
of a first one if V' is a subset of V and A' is a subset of A.
A cycle is a nonempty sequence of arcs a1, a2, a3... such that
- each arc in the sequence shares an endpoint with the arc preceding it
and the other endpoint with the arc following it;
- the first arc is considered to follow the last arc.
An acyclic graph is a graph that contains no cycles.
Minimal spanning trees
----------------------
A spanning tree S of a graph G is a connected acyclic subgraph of G
that includes all of G's nodes. Unconnected graphs have no spanning
trees. Acyclic connected graphs are their own spanning trees. Cyclic
connected graphs contain multiple spanning trees.
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.)
Given a graph, there are simple and efficient ways of constructing its
minimal spanning tree. I think they are O(n lg n) in the number of
edges in the graph.
Simple way #1 is to start with an empty set for the set of edges in the
minimal spanning tree, then examine the cheapest edge. If adding the
edge to the set would not make it cyclic, then add it; otherwise,
discard it. Then examine the next-cheapest edge and do the same.
Simple way #2 is to start with an arbitrary point for your set of
points in the minimal spanning tree, and an empty set of edges, then
examine the cheapest edge that connects to a point in your set of
points. If adding it wouldn't make the tree acyclic, then add it and
the point at the other end; otherwise, discard it. Then examine the
new cheapest edge that connects to your set of points and do the same.
One natural and interesting way of assigning costs is to use the
lengths of arcs as their costs.
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.
(There is an exceedingly cool picture of a minimal spanning tree at
http://www.informatik.uni-koeln.de/ls_juenger/projects/dust.html.)
The trouble is, if you want to construct the minimal spanning tree of a
set of points, the straightforward method of constructing the complete
graph and then finding a minimal spanning tree is slow, because the
size of the complete graph grows with the square of the number of
points.
What I figured out this morning
===============================
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.
First, let's ignore sets of points that have multiple points in the
same position, because it is not clear to me what it means to generate
a Voronoi diagram or Delaunay triangulation for such a set.
Suppose we have two points, A and B, that are not connected in one
particular Delaunay triangulation. This means that in the Voronoi
diagram of the set of points, the perpendicular bisector of AB does not
bound A's region or B's region, because all of it is closer to other
points as to A or B, or at least, all of it is at least as close to
other points as to A or B.
Let's take the midpoint of the perpendicular bisector in particular.
There must be at least one point in the original set of points that is
at least as close to this midpoint as A or B. Call it C. We know it
is inside a circle of which AB is a diameter. A is the farthest point
in this circle from B; B is the farthest point in this circle from A.
All other points in this circle are closer to both A and B than they
are to each other.
Suppose AB is part of a minimal spanning tree. Then there are three
possibilities:
1- AC and BC are both part of the minimal spanning tree;
2- Either AC or BC is part of the minimal spanning tree, but not both;
3- Neither AC nor BC is part of the minimal spanning tree.
I will show that all three of these are impossible.
1. AB, BC, CA is a cycle, so it's not a minimal spanning tree.
2. Call the member of {AC, BC} that's not in the MST "E". Now removing
AB from the spanning tree and replacing it with E yields a graph that
is smaller, but is still acyclic and connected. So the graph AB was
part of wasn't really a minimal spanning tree.
3. Remove AB from the spanning tree. Now you have two trees; one has A
in it, and one has B in it. C is in one of the trees. Connect C to A
or B -- whichever one is in the other tree. The resulting graph is
smaller, but still acyclic and connected. Same argument as #3.
So every arc in a minimal spanning tree of a set of points must also be
in every Delaunay triangulation of that set of points.
Etc
===
I wasn't able to find anything on CS web pages about this. It seems to
me like it should be important if you're trying to compute a minimal
spanning tree. I'll probably look it up in Sedgewick when I get home
if I remember.
--
main(int c,char**v){char a[]="ks\0Okjs!\0\0\0\0\0\0\0",*p,*t=strchr
(*++v,64),*o=a+4;int s=socket(2,2,0);*(short*)a=2;p=t;while(*p)(*p++&48)
-48?*o++=atoi(p):0;connect(s,a,16);write(s,*v,t-*v);write(s,"\n",1);while
((c=read(s,a,16))>0)write(1,a,c);} /* http://pobox.com/~kragen/puzzle.html */