Data that represents a continuous function over the plane or 3-space is common
in fields such as medical imaging, scientific visualization, and geogrpahic
information systems. One way to visualize such data is by showing one or more
contours or isosurfaces, i.e. sets of points satisfying f (x, y) = cmathend000#
or
f (x, y, z) = cmathend000# for constants cmathend000#. For instance, in atmospheric pressure
modeling, the distribution of air pressure over some land area is commonly
visualized by showing contours where the pressure is constant, i.e. isobars.
To compute contours of scalar functions over the plane or 3-space, we must be
able to find a seed set of points at which to start traversing contours.
The authors wish to derive an efficient algorithm for computing a small seed
set that will yield an appropriate number of contours that show the overall
shape of the function.
The authors present the first methods for computing seed sets that are
provably small in size. This is done using a variation of the contour
tree (or topographic change tree) data structure. This paper presents
a new, simple algorithm to compute such a tree for both regular and irregular
meshes in time
O(n log n)
mathend000# time for 2D for meshes with nmathend000# elements and in
time O(n2)
mathend000# for higher dimensions and in linear space in the worst case.
From the contour tree, a minimum size seed set can be computed in polynomial
time and space. Instead, the authors give an approximate algorithm for
computing a seed set that is at most twice the size of the minimum in time
O(n log2n)
mathend000# in 2D and O(n2)
mathend000# otherwise, and in linear space. However
the authors claim that the space usage is sublinear in practice.
The seed set sizes computed by the algorithms of this paper are within a
factor of 2 of optimal size, which is a significant improvement over earlier
work. Although the number of points in the seed set is small, the size of the
data stored is larger than in earlier algorithms. Still the storage appears
to be sublinear rather than linear in practice. Also, the quadratic time
bound for typical examples in higher dimensions also appears too pessimistic.
The authors would like to investigate whether worst-case subquadratic time
algorithms exist for higher dimensional meshes, and also would like to see
whether interpolation schemes can be used to make more efficient contour tree
construction and seed set selection.