@inproceedings{5293640db01d42aea93aef6908fc8e42,
title = "Locality and bounding-box quality of two-dimensional space-filling curves",
abstract = "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{\textquoteright}s measure, have good bounding-box quality, while the curve with the best-known locality has relatively bad bounding-box quality.",
author = "H.J. Haverkort and {Walderveen, van}, F.",
year = "2008",
doi = "10.1007/978-3-540-87744-8_43",
language = "English",
isbn = "978-3-540-87743-1",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "515--527",
editor = "D. Halperin and K. Mehlhorn",
booktitle = "Algorithms - ESA 2008 (16th Annual European Symposium, Karlsruhe, Germany, September 15-17, 2008, Proceedings)",
address = "Germany",
}