Locality and bounding-box quality of two-dimensional space-filling curves
type: Item
instance of: scholarly article
title: Locality and bounding-box quality of two-dimensional space-filling curves
zbMATH Open document ID: 1203.65045
author: Freek Van Walderveen
author: Herman Haverkort
published in: Computational Geometry
publication date: 2009-11-16T00:00:00Z
review text: The central objects of study of the paper are the the so-called space filling curves. These are continuous surjective mappings from \(\mathbb{R}\) to \(\mathbb{R}^d\). Beside the paper by \textit{G. Peano} [On a curve which entirely fills a plane domain. (Sur une courbe, qui remplit toute une aire plane.) Math. Ann. XXXVI. 157--160 (1890; JFM 22.0405.01)], one can check the reference [\textit{H. Sagan}, Space-filling curves. Universitext. New York: Springer-Verlag. xv, 193 p. (1994; Zbl 0806.01019)] for an extensive treatise of these type of geometric objects. In the introduction of the paper, some applications of space filling curves are commented. In this paper, the authors investigate which space filling curves are better in the sense of sorting points into bounding boxes with small total area and small total perimeter. For this purpose, the authors propose new quality measures to analyze how efficient the mapping are. In addition, they provide an algorithm to approximate these measures for a given curve.
reviewed by: J. Rafael Sendra
Mathematics Subject Classification ID: 65D18
zbMATH DE Number: 5633796
zbMATH Keywords: space-filling curves
zbMATH Keywords: spatial data structures
zbMATH Keywords: R-trees
MaRDI profile type: Publication
full work available at URL: j.comgeo.2009.06.002
OpenAlex ID: W2149107809
cites work: On multidimensional curves with Hilbert property
cites work: Infinite Series of Generalized Gosper Space Filling Curves
cites work: The priority R-tree
cites work: Space-filling curves and their use in the design of geometric data structures
cites work: The dilation factor of the Peano-Hilbert curve
cites work: Optimal linear arrangement of a rectangular grid
cites work: Q4740120
cites work: R-trees: theory and applications
cites work: Optimal Numberings of an $N \times N$ Array
cites work: Towards optimal locality in mesh-indexings
cites work: Space-filling curves
cites work: Über Peano-Kurven
DOI: 10.1016/J.COMGEO.2009.06.002
description: scientific article; zbMATH DE number 5633796