U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

PUBLICATIONS

In Order to Form a More Perfect UNION

Published

Author(s)

Isabel M. Beichl, F Sullivan

Abstract

In this computing prescription we present an algorithm for finding a minimum spanning tree figure 1 shows a typical application of this MST algorithm. Here we have 11 data points in a plane and would like to find some structure among them. Suppose we draw dotted linesbetween each pair of points (see Figure 1a). If we considerthe points vertices and the dotted lines edges, we have a complete graph on 11 points. In Figure 1b, we choose just enough of the edges to keep the graph connected. This is a spanning tree of the graph. A graph can have many spanning trees. The one shown is an MST-that is, a spanning tree that minimizes the total length of edges. Figure 2a displays another MST, this time for a set of 350 points. We have omitted the dotted lines because there would be 122,150 (350X349) of them. Figure 2b shows the MST for a set with structure, a sample from a chaotic attractor. Finding structure in complicated aggregates of points is one of the MST's main applications. An edge's weight is sometimes the distance between vertices, but not necessarily. It can be any weight associated with the connection. Of course, you can run this algorithm to maximize the weights too. The MST also arises in descriptions of the Ising model. In some formulations, the number of MSTs of some rectangular grid is the quantity to be approximated. You can find some of these results on the Web page of constants that Steven Finch maintains (www.mathsoft.com/asolve/constant/constant.html). Figure 2c shows an MST for points on a rectangular.grid. As we shall see, the hard part of this algorithm is implementing set UNIONs-thus, the article's title.
Citation
Computing in Science & Engineering
Volume
3
Issue
No. 2
Pub Type
Journals

Keywords

geometric algorithms, massive data, union find algorithm

Citation

Beichl, I. and Sullivan, F. (2001), In Order to Form a More Perfect UNION, Computing in Science & Engineering (Accessed December 11, 2024)

Issues

If you have any questions about this publication or are having problems accessing it, please contact reflib@nist.gov.

Created April 1, 2001, Updated February 17, 2017