Sampling from discrete distributions and computing Fréchet distances
Karl Bringmann · Max Planck Digital Library · 2014
In the first part of this dissertation, we study the fundamental problem of sampling from a discrete probability distribution. Specifically, given non-negative numbers p1, . . . , pn the task is to draw i with probability proportional to pi. We extend the classic solution to this problem, Walker’s alias method, in various directions: 1. We improve upon its space requirements by presenting optimal succinct sampling data structures. 2. We present improved trade-offs between preprocessing and query time for sorted inputs, and generalize this from proportional sampling to sampling subsets. 3. For Bernoulli, geometric, and binomial random variates we present optimal sampling algorithms on a bounded precision machine. 4. As an application, we speed up sampling of internal diffusion limited aggregation. The second part of this dissertation belongs to the area of computational geometry and deals with algorithms for the Frechet 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. Our various extensions of this main result include conditional lower bounds under realistic input assumptions, which do not match the known algorithms. We close this gap by presenting an improved approximation algorithm for the Frechet distance.