Laufzeit Bereichsanfragen < Algorithm. Geometrie < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 10:46 Mo 25.01.2010 | | Autor: | Daferni |
| Aufgabe | | Ein k-d-Baum kann auch für dreieckige Bereichsanfragen benutzt werden. Zeige, dass die Laufzeit für dreieckige Bereichsanfragen mit einem 2-d-Baum im schlimmsten Fall linear ist, auch wenn die Größe der Antwort Null ist. |
Hallo,
ich habe versucht diese Aufgabe zu Lösen bzw. auf den korrekten Lösungsweg zu stoßen indem ich mir Skizzen gemacht habe allerdings bin ich dadurch nicht viel weiter gekommen. Ich nehme an, dass die lineare Laufzeit mit der Suche nach dem Median zu tun hat(mittlerer Punkt), an dessen Stelle man die Mengen teilt, diesen Schritt führt man rekursiv durch um letztlich einem Suchbaum zu erhalten indem man dann wieder in O(log n) suchen kann.
Da man also in Dreiecke teilen soll, muss man also (im 2-d) nach 3 Koordinatenachsen sortieren(zB x-y-xy). Aber wie man an die Laufzeit ran geht bleibt mir noch verschlossen.
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 11:20 Mi 27.01.2010 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
