KIT | KIT-Bibliothek | Impressum
Open Access Logo
§
Volltext
URN: urn:nbn:de:swb:90-AAA177961

On the Manhattan-distance between points on space-filling mesh-indexings

Niedermeier, Rolf; Sanders, Peter

Abstract:

Indexing schemes based on space filling curves like the Hilbert
curve are a powerful tool for building efficient parallel
algorithms on mesh-connected computers. The main reason is that
they are locality-preserving, i.e., the Manhattan-distance between
processors grows only slowly with increasing index differences.
We present a simple and easy-to-verify proof that the Manhattan-
distance of any indices i and j is bounded by 3*sqrt{


Zugehörige Institution(en) am KIT Informatik für Ingenieure und Naturwissenschaftler (Inf. für Ing. u. Naturwiss.)
Publikationstyp Buch
Jahr 1996
Sprache Englisch
Identifikator KITopen ID: 17796
Erscheinungsvermerk Karlsruhe 1996. (Interner Bericht. Fakultät für Informatik, Universität Karlsruhe. 1996,18.)
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft KITopen Landing Page