Kapitel 4 – Bereichssuche

Folien: 📄 04-rangesearch.pdf · Praktikumsaufgabe 3 (2d-Bäume)

Gegeben ist eine feste Punktmenge, auf die viele Anfragen kommen: „Welche Punkte liegen in diesem achsenparallelen Rechteck?“ Dafür baut man einmal eine Datenstruktur (Vorverarbeitung) und beantwortet dann jede Anfrage schnell.

Das Kapitel ist ein Lehrstück für den Tausch Speicher gegen Anfragezeit:

Struktur	Speicher	Anfrage (2d)
alle Punkte testen	$O(n)$	$O(n)$
kd-Baum	$O(n)$	$O(\sqrt n + R)$
Range-Tree	$O(n\log n)$	$O(\log^2 n + R)$

$R$ = Anzahl der Punkte im Anfragebereich (Ausgabegröße).

Aufbau

Abschnitt	Inhalt
4.1–4.2 Problem & Ansätze	Datenbank-Beispiel, naiv, Gitter, BSP-Bäume
4.3 kd-Bäume	Aufbau am Median, Bereichssuche, $O(\sqrt n + R)$
4.4 Range-Trees	1d-Bereichssuche, kanonische Teilmengen, assoziierte Strukturen, Vergleich