The Hilbert (recursive) 2D mesh indexing, also known as a space filling curve, has recently found many applications in parallel computing and combinatorial optimisation due to its locality preserving property: given a pair of 2D meshnodes with indices i and j, the Manhattan distance betweeen these nodes is boudned as O(sp root i-j). For an application it is desirable that the constant factor hidden in the big-O and the evaluation time of an indexing scheme are minimised. In this paper we suggest a class of locality preserving indexing schemes of a 3D mesh with a smaller constant factor than previorsly known. We evaluate the constatn factors for a number of easy to compute indexing schemes in meshes of size up to 32~3 and provide asymptotic analytical boudns.
展开▼