Browse Theses

This thesis investigates the design of geometric algorithms, the worst-case running time of which is asymptotically equivalent (within a constant factor) to the expected running time of existing randomized algorithms--a process we call "derandomization." We derive an algorithm computing the convex hull of n points in $\IR\sp{d}$ running in $O(n\sp{\lfloor d/2\rfloor} + n\log n$) time, for any fixed dimension $d \ge$ 2. We give an algorithm that, for a set of n points in the plane, computes the connecting line whose slope is the median between all such lines. We also show how to approximate the NP-hard problem of finding a polytope having the minimum number of facets that separates two given nested polytopes in $\IR\sp{d}$, with $d \ge$ 3. If the minimum number of facets of such a polytope is c, we never return more than $O(c\log c$), and even improve to $O(c$) in $\IR\sp3$.

By making random choices during their execution, randomized algorithms guarantee a short expected running time, which sometimes is within a constant factor of optimal. To derandomize these algorithms, we actually compute the random choices, so as to fulfill the properties that guarantee a short running time to the randomized algorithms.

We show how a number of these properties can be captured by set systems. The set systems occurring in the randomized algorithms solving the problems mentioned above all have finite VC-dimension. (This VC-dimension is a combinatorial index that measures the complexity of the set system.) This implies that small random samples obey the properties that guarantee a short running time. We supply efficient deterministic methods for computing these samples and show various constructions that allow to estimate the geometric quantities in our algorithms. Therefore, the algorithms we derive do not perform any random choice, and retain the same running time (with at most constant factor overhead).