Harmonious Hilbert curves and other extradimensional space-filling curves

H.J. Haverkort

Research output: Book/ReportReportAcademic

Abstract

This paper introduces a new way of generalizing Hilbert's two-dimensional space-filling curve to arbitrary dimensions. The new curves, called harmonious Hilbert curves, have the unique property that for any d' <d, the d-dimensional curve is compatible with the d'-dimensional curve with respect to the order in which the curves visit the points of any d'-dimensional axis-parallel space that contains the origin. Similar generalizations to arbitrary dimensions are described for several variants of Peano's curve (the original Peano curve, the coil curve, the half-coil curve, and the Meurthe curve). The d-dimensional harmonious Hilbert curves and the Meurthe curves have neutral orientation: as compared to the curve as a whole, arbitrary pieces of the curve have each of d! possible rotations with equal probability. Thus one could say these curves are `statistically invariant' under rotation---unlike the Peano curves, the coil curves, the half-coil curves, and the familiar generalization of Hilbert curves by Butz and Moore. In addition, prompted by an application in the construction of R-trees, this paper shows how to construct a 2d-dimensional generalized Hilbert or Peano curve that traverses the points of a certain d-dimensional diagonally placed subspace in the order of a given d-dimensional generalized Hilbert or Peano curve. Pseudocode is provided for comparison operators based on the curves presented in this paper
Original languageEnglish
Publishers.n.
Number of pages40
Publication statusPublished - 2012

Publication series

NamearXiv.org
Volume1211.0175 [cs.CG]

Fingerprint

Space-filling Curves
Hilbert
Curve
Coil
Arbitrary

Cite this

Haverkort, H. J. (2012). Harmonious Hilbert curves and other extradimensional space-filling curves. (arXiv.org; Vol. 1211.0175 [cs.CG]). s.n.
Haverkort, H.J. / Harmonious Hilbert curves and other extradimensional space-filling curves. s.n., 2012. 40 p. (arXiv.org).
@book{165ba096c4984866a8987f9d704154ff,
title = "Harmonious Hilbert curves and other extradimensional space-filling curves",
abstract = "This paper introduces a new way of generalizing Hilbert's two-dimensional space-filling curve to arbitrary dimensions. The new curves, called harmonious Hilbert curves, have the unique property that for any d' <d, the d-dimensional curve is compatible with the d'-dimensional curve with respect to the order in which the curves visit the points of any d'-dimensional axis-parallel space that contains the origin. Similar generalizations to arbitrary dimensions are described for several variants of Peano's curve (the original Peano curve, the coil curve, the half-coil curve, and the Meurthe curve). The d-dimensional harmonious Hilbert curves and the Meurthe curves have neutral orientation: as compared to the curve as a whole, arbitrary pieces of the curve have each of d! possible rotations with equal probability. Thus one could say these curves are `statistically invariant' under rotation---unlike the Peano curves, the coil curves, the half-coil curves, and the familiar generalization of Hilbert curves by Butz and Moore. In addition, prompted by an application in the construction of R-trees, this paper shows how to construct a 2d-dimensional generalized Hilbert or Peano curve that traverses the points of a certain d-dimensional diagonally placed subspace in the order of a given d-dimensional generalized Hilbert or Peano curve. Pseudocode is provided for comparison operators based on the curves presented in this paper",
author = "H.J. Haverkort",
year = "2012",
language = "English",
series = "arXiv.org",
publisher = "s.n.",

}

Haverkort, HJ 2012, Harmonious Hilbert curves and other extradimensional space-filling curves. arXiv.org, vol. 1211.0175 [cs.CG], s.n.

Harmonious Hilbert curves and other extradimensional space-filling curves. / Haverkort, H.J.

s.n., 2012. 40 p. (arXiv.org; Vol. 1211.0175 [cs.CG]).

Research output: Book/ReportReportAcademic

TY - BOOK

T1 - Harmonious Hilbert curves and other extradimensional space-filling curves

AU - Haverkort, H.J.

PY - 2012

Y1 - 2012

N2 - This paper introduces a new way of generalizing Hilbert's two-dimensional space-filling curve to arbitrary dimensions. The new curves, called harmonious Hilbert curves, have the unique property that for any d' <d, the d-dimensional curve is compatible with the d'-dimensional curve with respect to the order in which the curves visit the points of any d'-dimensional axis-parallel space that contains the origin. Similar generalizations to arbitrary dimensions are described for several variants of Peano's curve (the original Peano curve, the coil curve, the half-coil curve, and the Meurthe curve). The d-dimensional harmonious Hilbert curves and the Meurthe curves have neutral orientation: as compared to the curve as a whole, arbitrary pieces of the curve have each of d! possible rotations with equal probability. Thus one could say these curves are `statistically invariant' under rotation---unlike the Peano curves, the coil curves, the half-coil curves, and the familiar generalization of Hilbert curves by Butz and Moore. In addition, prompted by an application in the construction of R-trees, this paper shows how to construct a 2d-dimensional generalized Hilbert or Peano curve that traverses the points of a certain d-dimensional diagonally placed subspace in the order of a given d-dimensional generalized Hilbert or Peano curve. Pseudocode is provided for comparison operators based on the curves presented in this paper

AB - This paper introduces a new way of generalizing Hilbert's two-dimensional space-filling curve to arbitrary dimensions. The new curves, called harmonious Hilbert curves, have the unique property that for any d' <d, the d-dimensional curve is compatible with the d'-dimensional curve with respect to the order in which the curves visit the points of any d'-dimensional axis-parallel space that contains the origin. Similar generalizations to arbitrary dimensions are described for several variants of Peano's curve (the original Peano curve, the coil curve, the half-coil curve, and the Meurthe curve). The d-dimensional harmonious Hilbert curves and the Meurthe curves have neutral orientation: as compared to the curve as a whole, arbitrary pieces of the curve have each of d! possible rotations with equal probability. Thus one could say these curves are `statistically invariant' under rotation---unlike the Peano curves, the coil curves, the half-coil curves, and the familiar generalization of Hilbert curves by Butz and Moore. In addition, prompted by an application in the construction of R-trees, this paper shows how to construct a 2d-dimensional generalized Hilbert or Peano curve that traverses the points of a certain d-dimensional diagonally placed subspace in the order of a given d-dimensional generalized Hilbert or Peano curve. Pseudocode is provided for comparison operators based on the curves presented in this paper

M3 - Report

T3 - arXiv.org

BT - Harmonious Hilbert curves and other extradimensional space-filling curves

PB - s.n.

ER -