NASA Logo

NTRS

NTRS - NASA Technical Reports Server

Back to Results
Self-Avoiding Walks over Adaptive Triangular GridsIn this paper, we present a new approach to constructing a "self-avoiding" walk through a triangular mesh. Unlike the popular approach of visiting mesh elements using space-filling curves which is based on a geometric embedding, our approach is combinatorial in the sense that it uses the mesh connectivity only. We present an algorithm for constructing a self-avoiding walk which can be applied to any unstructured triangular mesh. The complexity of the algorithm is O(n x log(n)), where n is the number of triangles in the mesh. We show that for hierarchical adaptive meshes, the algorithm can be easily parallelized by taking advantage of the regularity of the refinement rules. The proposed approach should be very useful in the run-time partitioning and load balancing of adaptive unstructured grids.
Document ID
20020054501
Acquisition Source
Ames Research Center
Document Type
Preprint (Draft being sent to journal)
Authors
Heber, Gerd
(Delaware Univ. Newark, DE United States)
Biswas, Rupak
(NASA Ames Research Center Moffett Field, CA United States)
Gao, Guang R.
(Delaware Univ. Newark, DE United States)
Saini, Subhash
Date Acquired
September 7, 2013
Publication Date
January 1, 1998
Subject Category
Computer Programming And Software
Meeting Information
Meeting: 39th Symposium on Foundations of Computer Science
Location: Palo Alto, CA
Country: United States
Start Date: November 8, 1998
End Date: November 11, 1998
Sponsors: Foundation of Computer Science
Funding Number(s)
CONTRACT_GRANT: NAS2-14303
PROJECT: RTOP 519-40-12
Distribution Limits
Public
Copyright
Work of the US Gov. Public Use Permitted.
No Preview Available