Bereichsbaum: Unterschied zwischen den Versionen

GISWiki - Das freie Portal für Geoinformatik (GIS)
Wechseln zu: Navigation, Suche
 
(quelle: wikipedia)
 
Zeile 1: Zeile 1:
−
Ein '''Bereichsbaum''' ist eine [[:de:Datenstruktur|Datenstruktur]] für das Speichern einer [[:de:Menge|Menge]] von Punkten im k-dimensionalen reellen Raum <math> \mathbb{R} ^k</math>.
+
Ein '''Bereichsbaum''' ist eine [[:de:Datenstruktur|Datenstruktur]] für das Speichern einer [[:de:Menge|Menge]] von Punkten im k-dimensionalen reellen Raum.
 
Er wird in der [[:de:Informatik|Informatik]] im Bereich der algorithmischen [[:de:Geometrie|Geometrie]] eingesetzt und unterstützt effizient orthogonale Bereichsanfragen.
 
Er wird in der [[:de:Informatik|Informatik]] im Bereich der algorithmischen [[:de:Geometrie|Geometrie]] eingesetzt und unterstützt effizient orthogonale Bereichsanfragen.
  
 
== Anwendunggebiet ==
 
== Anwendunggebiet ==
 
Anwendung finden solche Datenstrukturen in [[Geoinformationssystem]]en. Hier werden sie verwendet, um geographische Objekte zu suchen. Geoinformstionssysteme verwalten die räumlichen Koordinaten dieser Objekte. Der Bereichsbaum unterteilt (partitioniert) nun die Objekte abhängig von ihren Koordindaten in Teilmengen. Dadurch kann später die Suche nach einem bestimmten Objekt auf einen kleinen Bereich eingegrenzt und damit erheblich beschleunigt werden. Solche Datenstrukturen werden auch als [[:de:Indexstruktur|Indexstruktur]] bezeichnet.
 
Anwendung finden solche Datenstrukturen in [[Geoinformationssystem]]en. Hier werden sie verwendet, um geographische Objekte zu suchen. Geoinformstionssysteme verwalten die räumlichen Koordinaten dieser Objekte. Der Bereichsbaum unterteilt (partitioniert) nun die Objekte abhängig von ihren Koordindaten in Teilmengen. Dadurch kann später die Suche nach einem bestimmten Objekt auf einen kleinen Bereich eingegrenzt und damit erheblich beschleunigt werden. Solche Datenstrukturen werden auch als [[:de:Indexstruktur|Indexstruktur]] bezeichnet.
−
 
−
== Mathematische Beschreibung ==
 
−
Im einfachsten Falle, also <math>\mathbb{R} ^1</math> ist der eindimensionale Bereichsbaum <math>T^1</math> ein gewöhnlicher binärer Suchbaum.
 
−
Allgemein ist der k-dimensionale Bereichsbaum <math>T^k</math> rekursiv definiert:
 
−
 
−
Seien {<math>x_1, x_2, ... , x_k</math>} die Koordinatenachsen des <math>\mathbb{R} ^k</math>
 
−
* Konstruiere zunächst einen 1-dimensionalen Bereichsbaum <math>T ^1</math> für die Koordinatenachse <math>x_1</math>, d.h. für 1-dimensionale Punkte, die sich durch abschneiden der hinteren k-1 Koordinaten ergeben.
 
−
* Konstruiere rekursiv für jeden inneren [[:de:Knoten|Knoten]] <math>v</math> des <math>T ^1</math> jeweils einen (k-1)-dimensionalen Bereichsbaum <math>T_v ^{k-1}</math> aus den (k-1)-dimensionalen Punkten, die sich durch abschneiden der ersten Koordinate ergeben.
 
−
* Verbinde Knoten <math>v</math> des <math>T^1</math> mit Hilfe eines [[:de:Zeiger (Informatik)|Zeigers]] mit dem zugehörigen <math>T_v ^{k-1}</math>
 
−
 
−
Der so aufgebaute Bereichsbaum unterstützt orthogonale Bereichsanfragen in
 
−
:<math>O(n*log(n))</math> Speicherplatz
 
−
:<math>O(log(n) ^k + a)</math> Zeit, wobei <math>a</math> die Größe der Antwort ist, d.h. die Anzahl der Punkte im Anfragerechteck.
 

Aktuelle Version vom 7. August 2005, 15:01 Uhr

Ein Bereichsbaum ist eine Datenstruktur für das Speichern einer Menge von Punkten im k-dimensionalen reellen Raum. Er wird in der Informatik im Bereich der algorithmischen Geometrie eingesetzt und unterstützt effizient orthogonale Bereichsanfragen.

Anwendunggebiet

Anwendung finden solche Datenstrukturen in Geoinformationssystemen. Hier werden sie verwendet, um geographische Objekte zu suchen. Geoinformstionssysteme verwalten die räumlichen Koordinaten dieser Objekte. Der Bereichsbaum unterteilt (partitioniert) nun die Objekte abhängig von ihren Koordindaten in Teilmengen. Dadurch kann später die Suche nach einem bestimmten Objekt auf einen kleinen Bereich eingegrenzt und damit erheblich beschleunigt werden. Solche Datenstrukturen werden auch als Indexstruktur bezeichnet.

Von „http://giswiki.org/index.php?title=Bereichsbaum&oldid=6626“