DLR-Logo -> http://www.dlr.de
DLR Portal Home | Imprint | Privacy Policy | Contact | Deutsch
Fontsize: [-] Text [+]

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

Burstedde, Carsten and Holke, Johannes and Isaac, Tobin (2019) On the Number of Face-Connected Components of Morton-Type Space-Filling Curves. Foundations of Computational Mathematics, 19 (4), pp. 843-868. Springer. doi: 10.1007/s10208-018-9400-5. ISSN 1615-3375.

[img] PDF - Postprint version (accepted manuscript)

Official URL: https://dx.doi.org/10.1007/s10208-018-9400-5


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.

Item URL in elib:https://elib.dlr.de/128742/
Document Type:Article
Title:On the Number of Face-Connected Components of Morton-Type Space-Filling Curves
AuthorsInstitution or Email of AuthorsAuthor's ORCID iDORCID Put Code
Burstedde, CarstenInstitut für Numerische Simulation (INS), Endenicher Allee 19b, 53115 Bonn, Germanyhttps://orcid.org/0000-0001-9843-1041UNSPECIFIED
Holke, JohannesGerman Aerospace Center (DLR), Linder Höhe, 51147 Köln, Germanyhttps://orcid.org/0000-0002-2783-3286UNSPECIFIED
Isaac, TobinCollege of Computing, Georgia Institute of Technology, North Avenue, Atlanta, GA 30332, USAhttps://orcid.org/0000-0002-2628-3585UNSPECIFIED
Date:1 August 2019
Journal or Publication Title:Foundations of Computational Mathematics
Refereed publication:Yes
Open Access:Yes
Gold Open Access:No
In ISI Web of Science:Yes
Page Range:pp. 843-868
EditorsEmailEditor's ORCID iDORCID Put Code
Keywords:Space-filling curve Adaptive mesh refinement Morton code
HGF - Research field:Aeronautics, Space and Transport
HGF - Program:Space
HGF - Program Themes:Space System Technology
DLR - Research area:Raumfahrt
DLR - Program:R SY - Space System Technology
DLR - Research theme (Project):R - Vorhaben SISTEC (old)
Location: Köln-Porz
Institutes and Institutions:Institut of Simulation and Software Technology > High Performance Computing
Deposited By: Holke, Johannes
Deposited On:06 Nov 2019 10:57
Last Modified:01 Sep 2020 03:00

Repository Staff Only: item control page

Help & Contact
electronic library is running on EPrints 3.3.12
Website and database design: Copyright © German Aerospace Center (DLR). All rights reserved.