Bitte benutzen Sie diese Referenz, um auf diese Ressource zu verweisen: doi:10.22028/D291-25417
Titel: Sampling from discrete distributions and computing Fréchet distances
Verfasser: Bringmann, Karl
Sprache: Englisch
Erscheinungsjahr: 2014
SWD-Schlagwörter: Randomisierter Algorithmus
Datenstruktur
untere Schranke
Freie Schlagwörter: sampling algorithm
Walker's alias method
curve similarity
Fréchet distance
strong exponential time hypothesis
DDC-Sachgruppe: 004 Informatik
Dokumentart : Dissertation
Kurzfassung: 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.
Link zu diesem Datensatz: urn:nbn:de:bsz:291-scidok-59883
hdl:20.500.11880/25473
http://dx.doi.org/10.22028/D291-25417
Erstgutachter: Mehlhorn, Kurt
Tag der mündlichen Prüfung: 17-Dez-2014
SciDok-Publikation: 26-Jan-2015
Fakultät: Sonstige Einrichtungen
Fachrichtung: SE - Max-Planck-Institut für Informatik
Fakultät / Institution:SE - Sonstige Einrichtungen

Dateien zu dieser Ressource:
Datei Beschreibung GrößeFormat 
thesis_final.pdf1,47 MBAdobe PDFÖffnen/Anzeigen


Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.