Answers are grounded in this paper and cite their sources.
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ᵈ. The algorithm is obtained by derandomization of a randomized incremental algorithm, and its running time of O(nlog n + n{ d/2})$ is optimal for any fixed dimension $d≥ 2$.
No takes yet. Share an insight, caveat, or question.
Brönnimann et al. (1999) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: