Triangulations of a surface are of fundamental importance in computational
geometry, computer graphics, and engineering and scientific simulations.
Triangulations are ordinarily represented as mutable graph structures for
which both adding and traversing edges take constant time per operation.
These representations of triangulations make it difficult to support
\emph{persistence}, including ``multiple futures'', the ability to use a data
structure in several unrelated ways in a given computation; ``time travel'',
the ability to move freely among versions of a data structure; or parallel
computation, the ability to operate concurrently on a data structure without
interference.
We present a purely functional interface and representation of triangulated
surfaces, and more generally of simplicial complexes in higher dimensions. In
addition to being persistent in the strongest sense, the interface more
closely matches the mathematical definition of triangulations (simplicial
complexes) than do interfaces based on mutable representations. The
representation, however, comes at the cost of requiring $O(\lg n)$ time for
traversing or adding triangles (simplices), where $n$ is the number of
triangles in the surface. We show both analytically and experimentally that
for certain important cases, this extra cost does not seriously affect
end-to-end running time. Analytically, we present a new randomized algorithm
for 3-dimensional Convex Hull based on our representations for which the
running time matches the $\Omega(n \lg n)$ lower-bound for the problem. This
is achieved by using only $O(n)$ traversals of the surface. Experimentally,
we present results for both an implementation of the 3-dimensional Convex Hull
and for a terrain modeling algorithm, which demonstrate that, although there
is some cost to persistence, it seems to be a small constant factor.