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?


Log in to reply