Product range spaces, sensitive sampling, and derandomization

We introduce the concept of a sensitive ε-approximation and use it to derive a more efficient algorithm for computing ε-nets. We define and investigate product range spaces, for which we establish sampling theorems analogous to the standard finite VC-dimensional case. This generalizes and simplifies results from previous works. Using these tools, we give a new deterministic algorithm for computing the convex hull of n points in R^d. The algorithm is obtained by derandomization of a randomized incremental algorithm, and its running time of O(n log n + n^[d/2]) is optimal for any fixed dimension d ≥ 2.