elib
DLR-Header
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 (2018) On the Number of Face-Connected Components of Morton-Type Space-Filling Curves. Foundations of Computational Mathematics, pp. 1-26. Springer. DOI: 10.1007/s10208-018-9400-5 ISSN 1615-3375 (In Press)

WarningThere is a more recent version of this item available.

[img] PDF
779kB

Official URL: https://rdcu.be/bcxNo

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.

Item URL in elib:https://elib.dlr.de/124370/
Document Type:Article
Title:On the Number of Face-Connected Components of Morton-Type Space-Filling Curves
Authors:
AuthorsInstitution or Email of AuthorsAuthors ORCID iD
Burstedde, CarstenInstitut für Numerische Simulation (INS), Endenicher Allee 19b, 53115 Bonn, Germanyhttps://orcid.org/0000-0001-9843-1041
Holke, JohannesGerman Aerospace Center (DLR), Linder Höhe, 51147 Köln, Germanyhttps://orcid.org/0000-0002-2783-3286
Isaac, TobinCollege of Computing, Georgia Institute of Technology, North Avenue, Atlanta, GA 30332, USAhttps://orcid.org/0000-0002-2628-3585
Date:5 October 2018
Journal or Publication Title:Foundations of Computational Mathematics
Refereed publication:Yes
Open Access:Yes
Gold Open Access:No
In SCOPUS:Yes
In ISI Web of Science:Yes
DOI :10.1007/s10208-018-9400-5
Page Range:pp. 1-26
Editors:
EditorsEmail
Cohen, Albertjofocm@gmail.com
Munthe-Kass, HansUNSPECIFIED
Publisher:Springer
ISSN:1615-3375
Status:In Press
Keywords:Space-filling curve Adaptive mesh refinement Morton code
HGF - Research field:Aeronautics, Space and Transport
HGF - Program:Space
HGF - Program Themes:Space Technology
DLR - Research area:Raumfahrt
DLR - Program:R SY - Technik für Raumfahrtsysteme
DLR - Research theme (Project):R - Vorhaben SISTEC
Location: Köln-Porz
Institutes and Institutions:Institut of Simulation and Software Technology > High Performance Computing
Deposited By: Holke, Johannes
Deposited On:07 Dec 2018 14:27
Last Modified:01 Dec 2019 03:00

Available Versions of this Item

Repository Staff Only: item control page

Browse
Search
Help & Contact
Information
electronic library is running on EPrints 3.3.12
Copyright © 2008-2017 German Aerospace Center (DLR). All rights reserved.