Sampling from discrete distributions and computing Fréchet distances

Abstract

In the first part of this thesis, we study the fundamental problem of sampling from a discrete probability distribution. Specifically, given non-negative numbers p_1,...,p_n the task is to draw i with probability proportional to p_i. We extend the classic solution to this problem, Walker's alias method, in various directions: We improve its space requirements, we solve the special case of sorted input, we study sampling natural distributions on a bounded precision machine, and as an application we speed up sampling a model from physics. The second part of this thesis belongs to the area of computational geometry and deals with algorithms for the Fréchet distance, which is a popular measure of similarity of two curves and can be computed in quadratic time (ignoring logarithmic factors). We provide the first conditional lower bound for this problem: No polynomial factor improvement over the quadratic running time is possible unless the Strong Exponential Time Hypothesis fails. We also present an improved approximation algorithm for realistic input curves.

Im ersten Teil dieser Dissertation untersuchen wir das fundamentale Problem des Ziehens einer Zufallsvariablen von einer gegebenen diskreten Wahrscheinlichkeitsverteilung. Die Aufgabe ist, gegeben nichtnegative Zahlen p_1,...,p_n, eine Zahl i mit Wahrscheinlichkeit proportional zu p_i zu ziehen. Wir erweitern die klassische Lösung dieses Problems, Walkers Aliasmethode, in verschiedene Richtungen: Wir verbessern ihren Speicherbedarf, wir lösen den Spezialfall von sortierter Eingabe, wir untersuchen das Ziehen von natürlichen Verteilungen auf Maschinen mit beschränkter Präzision, und als Anwendung beschleunigen wir die Simulation eines physikalischen Modells. Der zweite Teil dieser Dissertation gehört zum Gebiet der Computergeometrie und beschäftigt sich mit Algorithmen für die Fréchetdistanz, die ein beliebtes Ähnlichkeitsmaß zweier Kurven ist und in quadratischer Zeit berechnet werden kann (bis auf logarithmische Faktoren). Wir zeigen die erste bedingte untere Schranke für dieses Problem: Keine Verbesserung um einen polynomiellen Faktor ist möglich unter der starken Exponentialzeithypothese. Zudem präsentieren wir einen verbesserten Approximationsalgorithmus für realistische Eingabekurven.