On the Number of Face-Connected Components of Morton-Type Space-Filling Curves

Abstract

The Morton- or z-curve is one example for a space-filling curve: Given a level of refinement L iit maps the interval [0, 2^(dL)) one-to-one to a set of d-dimensional cubes of edge length 2^-L that form a subdivision of the unit cube. Similar curves have been proposed for triangular and tetrahedral unit domains. In contrast to the Hilbert curve that is continuous, the Morton-type curves produce jumps between disconnected subdomains. We prove that any contiguous subinterval of the curve divides the domain into a bounded number of face-connected subdomains. For the hypercube case in arbitrary dimension, the subdomains are star-shaped and the bound is indeed two. For the simplicial case in dimension 2, the bound is 2(L - 1), and in dimension 3 it is 2L + 1, where L is the depth of refinement. We supplement the paper with theoretical and computational studies on the distribution of the number of jumps. For the hypercube curve, we can characterize the distribution by the fraction of segments of a given length that have no jump, and find that the fraction has a lower bound of 1/(2^d -1) and an asymptotic upper bound of 1/2. For the simplicial curve, over 90% of all segments have three components or less.