Product range spaces, sensitive sampling, and derandomization

Hervé Brönnimann, Bernard Chazelle, Jiří Matoušek

Research output: Contribution to journalArticlepeer-review

31 Scopus citations


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 languageEnglish (US)
Pages (from-to)1552-1575
Number of pages24
JournalSIAM Journal on Computing
Issue number5
StatePublished - 1999

All Science Journal Classification (ASJC) codes

  • General Computer Science
  • General Mathematics


Dive into the research topics of 'Product range spaces, sensitive sampling, and derandomization'. Together they form a unique fingerprint.

Cite this