Generierung diskreter Zufallsvariablen und Berechnung der Fréchetdistanz

Abstract

Im ersten Teil dieser Dissertation untersuchen wir das fundamentale Problem der Generierung von Zufallsvariablen mit einer gegebenen diskreten Wahrscheinlichkeitsverteilung. Wir erweitern die klassische Lösung dieses Problems, Walkers Aliasmethode, in verschiedene Richtungen: Wir verbessern ihren Speicherbedarf, lösen den Spezialfall von sortierter Eingabe und untersuchen das Ziehen von natürlichen Verteilungen auf Maschinen mit beschränkter Präzision. Als Anwendung beschleunigen wir die Simulation eines physikalischen Modells. Der zweite Teil dieser Dissertation gehört zum Gebiet der Geometrie und handelt von Algorithmen für die Fréchetdistanz, einem beliebten Ähnlichkeitsmaß für Kurven, das in quadratischer Zeit berechnet werden kann (bis auf logarithmische Faktoren). Wir zeigen die erste bedingte untere Schranke für dieses Problem: Unter der starken Exponentialzeithypothese ist keine Verbesserung der quadratischen Laufzeit um einen polynomiellen Faktor möglich. Zusätzlich präsentieren wir einen verbesserten Approximationsalgorithmus für realistische Eingabekurven.