Delaunay-Triangulierung



  • Hallo!

    Ich beschäftige mich derzeit im Studium mit der Delaunay-Triangulierung - speziell: Randomisiert Inkrementelle Konstruktion der Delaunay Triangulierung. Dabei bin ich darauf gestoßen, dass das Verfahren der Inkrementellen Konstruktion schlechter ist, als das Randomisierte. Beweise gibt es von Guibas/Knuth, jedoch erkenne ich nicht ganz klar die Motivation warum man eine zufällige Permutation der Punktemenge erzeugt und dadurch hoff das Verfahren verbessern zu können.

    Kennt sich jemand mit diesem Thema aus und kann mir dort eine kleine Hilfe geben?

    Vielen Dank!



  • Laut Rolf Kleins Buch "Algorithmische Geometrie" hat die inkrementelle Konstruktion der DT eine mittlere Laufzeit von O (n log(n)), falls die Permutationen der Punkte in der Eingabe alle gleich wahrscheinlich sind.
    Der worst-case ist quadratisch.

    Angenommen, man kennt die worst-case-Permutation und gibt immer genau diese in den nicht randomisierten Algorithmus. Dann kommt immer worst-case-Laufzeit raus, also auch im Mittel, weil der worst-case dann Wahrscheinlichkeit 1 hat.
    Bei der randomisierten Konstruktion bekommt man in diesem Fall immer noch mittlere Laufzeit O (n log(n)), ganz unabhängig von den Wahrscheinlichkeiten der Eingabe-Permutationen.

    Da man bei den Anwendungen die Wahrscheinlichkeits-Verteilung nicht kennt, und man trotzdem im Mittel die Laufzeit O (n log(n)) haben möchte, randomisiert man, um nicht so einen Fall mit Dauer-worst-case zu riskieren.
    Natürlich nimmt man dann in Kauf, dass auch gute Verteilungen zerstört werden, aber wenn man nicht weiß was die Eingabe-Verteilung ist, bekommt man so wenigstens eine relativ gute Aussage über die mittlere Laufzeit.

    Das ist die Motivation für die Randomisierung, so wie ich sie aus dem Buch verstanden habe. Ich hoffe, das hilft.


Log in to reply