Z-Kurve

Z-Kurve

Die Z-Kurve (Lebesgue-Kurve) ist eine raumfüllende Kurve, die in der Informatik für mehrdimensionale Datenstrukturen verwendet wird. Der Z-Wert eines Raumpunktes wird einfach durch bitweises Verschränken der Koordinatenwerte berechnet (Bit Interleaving). Da raumfüllende Kurven die Daten auf eine Dimension abbilden, kann jede eindimensionale Datenstruktur verwendet werden, wie z. B. eine einfache Tabelle, eine Skip-Liste, ein binärer Suchbaum, ein B-Baum, oder ein B+-Baum. Im letzteren Fall wird er nach Rudolf Bayer UB-Baum (Universal B-Tree) genannt.

Die Z-Kurve ist beliebt aufgrund ihrer guten Nachbarschaftserhaltung und der einfachen Berechenbarkeit der Z-Werte. Bei der Hilbert-Kurve ist die Nachbarschaftserhaltung besser, doch sind die Berechnungen komplizierter.

Unter Weglassung gering signifikanter Bits kann man die Z-Werte für Hashtabellen verwenden, in denen Nachbarschaftssuchen möglich sind.

Z-CURVE.jpg

Diese Abbildung zeigt die Z-Werte für den zweidimensionalen Fall mit den Koordinaten x=0..7, y=0..7; folgt man den Werten, so erhält man eine rekursiv Z-förmige Kurve.

Trotz der guten Nachbarschaftserhaltung ist für die mehrdimensionale Bereichssuche ein Algorithmus erforderlich, um, ausgehend von einem in der Datenstruktur außerhalb des Suchbereichs angetroffenen Punkt, den nächsten Z-Wert zu bestimmen, dessen Koordinaten im Suchbereich liegen.

BIGMIN.jpg

In diesem Beispiel ist der Suchbereich (x=2..3, y=2..6) mit dem gepunkteten Rechteck angezeigt. Der höchste Z-Wert darin (MAX) ist 45. Angenommen, im Laufe der Suche wird der Wert F=19 angetroffen, bei Suche nach steigenden Werten. Dann müsste man das Intervall zwischen F und Max durchsuchen (schraffiertes Gebiet). Um die Suche zu beschleunigen, berechnen wir den nächsten Z-Wert im Suchbereich, im folgenden BIGMIN genannt (36 im Beispiel). Dann muss nur das Intervall zwischen BIGMIN and MAX durchsucht werden (fett gezeichnete Werte), dadurch wird der Großteil des schraffierten Gebiets übersprungen. Die Suche nach fallenden Werten ist analog dazu, mit LITMAX, dem größten Z-Wert im Suchbereich, der kleiner ist als F. Das Problem und seine Lösung wurde zuerst beschrieben in [1]. Die Lösung wird ebenso verwendet im UB-Baum („GetNextZ-address“).

Indem man die Methode hierarchisch (entsprechend der verwendeten Datenstruktur) einsetzt, ggf. nach sowohl steigenden als auch fallenden Z-Werten, erhält man eine hocheffiziente mehrdimensionale Bereichssuche; dies ist nützlich sowohl in kommerziellen als auch technischen Anwendungen, z. B. als Grundfunktion für (Nächste-) Nachbarschaftssuchen.

BIGMIN Quellcode für Z-Kurve und Hilbert-Kurve findet man in [2].

Einzelnachweise

  1. ↑ [1] H. Tropf, H. Herzog: Multidimensional Range Search in Dynamically Balanced Trees, Angewandte Informatik, 2/1981, pp 71–77.
  2. ↑ H. Tropf: US Patent 7,321,890

Wikimedia Foundation.

Игры ⚽ Поможем сделать НИР

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Kurve — »gekrümmte Linie, Bogen‹linie›; Straßen , Fahrbahnkrümmung«: Das seit dem 18. Jh., zuerst als geometrischer Terminus bezeugte Wort hat sich aus lat. curva linea »gekrümmte Linie« verselbstständigt. Das zugrunde liegende Adjektiv lat. curvus… …   Das Herkunftswörterbuch

  • Kurve — steht für einen Bogen im Sinne des Straßen und Schienenbaus, siehe Trassierungselement, einen Teil eines Stadions, siehe Fankurve, und verschiedene mathematische Objekte, nämlich für eindimensionale Objekte, die im Allgemeinen eine Krümmung… …   Deutsch Wikipedia

  • Kurve — (lat.), in der Geometrie zunächst eine krumme Linie im Gegensatze zur Geraden, doch rechnet man, wenn man von Kurven überhaupt spricht, gewöhnlich auch die geraden Linien dazu, indem man sie als Kurven betrachtet, deren Krümmung (s. d.) gleich… …   Meyers Großes Konversations-Lexikon

  • Kurve — Sf std. (18. Jh.) Entlehnung. Entlehnt aus l. curva (līnea) gekrümmte Linie , dem Femininum von l. curvus krumm, gekrümmt, gebogen, gewölbt . Zunächst ein Wort der Mathematik. Verb: kurven.    Ebenso nndl. curve, ne. curve, nfrz. courbe, nschw.… …   Etymologisches Wörterbuch der deutschen sprache

  • Kurve — [Aufbauwortschatz (Rating 1500 3200)] Bsp.: • Die Straße macht eine scharfe Kurve …   Deutsch Wörterbuch

  • Kurve — (lat.), krumme Linie, heißt, wenn sie in einer einzigen Ebene liegt, ebene K. (K. von einfacher Krümmung), im andern Falle Raum K. (K. von doppelter Krümmung). Die Natur der Krümmung ist bekannt, wenn die Beziehungen zwischen den Koordinaten (s.d …   Kleines Konversations-Lexikon

  • Kurve gleicher Lautstärke — Kurve (f) gleicher Lautstärke, Isophonkurve (f) eng equal loudness contour …   Arbeitssicherheit und Gesundheitsschutz Glossar

  • Kurve (Mathematik) — In der Mathematik ist eine Kurve ein eindimensionales Objekt. Eindimensional bedeutet dabei informell, dass man sich auf der Kurve nur in einer Richtung (bzw. der Gegenrichtung) bewegen kann. Ob die Kurve in der zweidimensionalen Ebene liegt… …   Deutsch Wikipedia

  • Kurve (algebraische Geometrie) — Eine algebraische Kurve ist eine eindimensionale algebraische Varietät, kann also durch eine Polynomgleichung beschrieben werden. Ein wichtiger Spezialfall sind die ebenen algebraischen Kurven, also algebraische Kurven, die in der affinen oder… …   Deutsch Wikipedia

  • Kurve — Schleife (eines Flusses); Biegung; Krümmung; Bogen; gekrümmte Linie * * * Kur|ve [ kʊrvə], die; , n: 1. Biegung, Krümmung einer Straße, eines Verkehrsweges: eine scharfe, enge, unübersichtliche Kurve; der Wagen wurde aus der Kurve getragen; eine… …   Universal-Lexikon

  • Kurve — Kụr·ve [ və] die; , n; 1 eine (regelmäßig gekrümmte) Linie ohne Ecken, in der Form eines Bogens ↔ Gerade <etwas bildet eine Kurve, stellt eine Kurve dar>: Das Flugzeug beschrieb / flog eine weite Kurve 2 eine Stelle, an der eine Straße… …   Langenscheidt Großwörterbuch Deutsch als Fremdsprache

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”