Minimum Spanning Trees
- Applications of computational geometry.
John Hershberger describes some geometric problems arising in his work
at Mentor graphics including interpolation of thermal data, minimum spanning trees, and breakout
routing in PC board design.
- Cancer
imaging. The BC Cancer Research Ctr. uses minimum spanning trees to
describe the arrangements of nuclei in skin cells.
- Cosmology at
the University of Kentucky. This group works on large-scale
structure formation, using methods including N-body simulations and
minimum spanning trees.
- Detecting actin fibers in cell images.
A. E. Johnson and
R. E. Valdes-Perez use minimum spanning trees for biomedical image analysis.
- The
Euclidean minimum spanning tree mixing model. S. Subramaniam and
S. B. Pope use geometric minimum spanning trees to model locality of
particle interactions in turbulent fluid flows. The tree structure of
the MST permits a linear-time solution of the resulting
particle-interaction matrix.
- Extracting features from remotely sensed images. Mark Dobie and co-workers use minimum spanning trees to find road networks in satellite and aerial imagery.
- Finding
quasar superstructures.
M. Graham and co-authors use 2d and 3d minimum spanning
trees for finding clusters of quasars and Seyfert galaxies.
- Learning
salient features for real-time face verification, K. Jonsson, J. Matas,
and J. Kittler. Includes a minimum-spanning-tree based algorithm
for registering the images in a database of faces.
- Minimal
spanning tree analysis of fungal spore spatial patterns,
C. L. Jones, G. T. Lonergan, and D. E. Mainwaring.
- A minimal spanning tree analysis of the CfA redshift survey. Dan Lauer uses minimum spanning trees to understand the large-scale structure of the universe.
- A
mixing model for turbulent reactive flows based on Euclidean minimum
spanning trees, S. Subramaniam and S. B. Pope.
- Sausages,
proteins, and rho. In the talk announced here, J. MacGregor Smith
discusses Euclidean Steiner tree theory and describes potential
applications of Steiner trees to protein conformation and molecular
modeling.
- Weather
data interpretation. The Insight group at Ohio State is using
geometric techniques such as minimum spanning trees to extract features
from large meteorological data sets.
Part of
Geometry in Action,
a collection of applications of computational geometry.
David Eppstein,
Theory Group,
ICS,
UC Irvine.
Semi-automatically
filtered
from a common source file.
