Well Separated Pair Decomposition
-
Ich beziehe mich auf folgenden Buchausschnitt:
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.94.9691&rep=rep1&type=pdf
Auf Seite 42 wird eine geometrische Distanz eingeführt.
Ich habe damit ein Problem.Wie deute ich diese Distanz?
Ich habe zwei Möglichkeiten im Kopf:1. Die Distanz zwischen zwei Quadtree-Zellen u und v:
Das würde bedeuten, dass benachbarte Knoten immer Abstand Null hätten. Das würde für mich abwer auch bedeuten, dass das im Beispiel vorkommende Paar {a,b,c},{e}
nicht legal wäre.2. Die Distanz zwischen den Punkten der Punktmenge P in den Knoten u und v.
Dann wäre für mich aber d(u,v) = d(P_u, P_v) und das wäre im Beweis von Lemma 3.1.4 nicht gut.
Ohnehin: Wo kommt im Beweis von 3.1.4 dieses epsilon/8 her?