Locality and bounding-box quality of two-dimensional space-filling curves

H.J. Haverkort, F. Walderveen, van

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

4 Citations (Scopus)


Space-filling curves can be used to organise points in the plane into bounding-box hierarchies (such as R-trees). We develop measures of the bounding-box quality of space-filling curves that express how effective different curves are for this purpose. We give general lower bounds on the bounding-box quality and on locality according to Gotsman and Lindenbaum for a large class of curves. We describe a generic algorithm to approximate these and similar quality measures for any given curve. Using our algorithm we find good approximations of the locality and bounding-box quality of several known and new space-filling curves. Surprisingly, some curves with bad locality by Gotsman and Lindenbaum’s measure, have good bounding-box quality, while the curve with the best-known locality has relatively bad bounding-box quality.
Original languageEnglish
Title of host publicationAlgorithms - ESA 2008 (16th Annual European Symposium, Karlsruhe, Germany, September 15-17, 2008, Proceedings)
EditorsD. Halperin, K. Mehlhorn
Place of PublicationBerlin
ISBN (Print)978-3-540-87743-1
Publication statusPublished - 2008

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743


Dive into the research topics of 'Locality and bounding-box quality of two-dimensional space-filling curves'. Together they form a unique fingerprint.

Cite this