Self-avoiding walks over adaptive unstructured grids

摘要

In this paper, we present self-avoiding walks as a novel technique to 'linearize' an unstructured mesh. Unlike space-filling curves which are based on a geometric embedding, our strategy is combinatorial since It uses the mesh connectivity only. We formulate a linear time-complexity algorithm for the construction Of these self-avoiding walks over a triangular mesh. We also show how the concept can be easily modified For adaptive grids that are generated in a hierarchical manner based on a set of simple rules, and made Amenable for efficient parallelization. We suggest a metric that might be used to evaluate the quality of such Walks and present some sample results. The proposed locality-enhancing approach should be very useful in The runtime partitioning and load balancing of adaptive unstructured grids. Copyright