Persistent triangulations

Triangulations of a surface are of fundamental importance in computational geometry, computer graphics, and engineering and scientific simulations. Tr iangulations are ordinarily represented as mutable graph structures for whi ch both adding and traversing edges take constant time per operation. These representations of triangulations make it difficult to support persistence , including 'multiple futures" the ability to use a data structure in sever al unrelated ways in a given computation; 'time travel', the ability to mov e freely among versions of a data structure; or parallel computation, the a bility to operate concurrently on a data structure without interference. We present a purely functional interface and representation of triangulated s urfaces, and more generally of simplicial complexes in higher dimensions. I n addition to being persistent in the strongest sense, the interface more c losely matches the mathematical definition of triangulations (simplicial co mplexes) than do interfaces based on mutable representations. The represent ation, however, comes at the cost of requiring O(Ign) time for traversing o r adding triangles (simplices), where n is the number of triangles in the s urface. We show both analytically and experimentally that for certain impor tant cases, this extra cost does not seriously affect end-to-end running ti me. Analytically, we present a new randomized algorithm for 3-dimensional C onvex 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 o nly O(n) traversals of the surface. Experimentally, we present results for both an implementation of the 3-dimensional Convex Hull and for a terrain m odeling algorithm, which demonstrate that, although there is some cost to p ersistence, it seems to be a small constant factor.