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 Rd. 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.
|Original language||English (US)|
|Number of pages||24|
|Journal||SIAM Journal on Computing|
|State||Published - 1999|
All Science Journal Classification (ASJC) codes
- Computer Science(all)