Product range spaces, sensitive sampling, and derandomization

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

Research output: Contribution to journalArticle

25 Scopus citations

Abstract

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
Volume28
Issue number5
DOIs
StatePublished - 1999

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Mathematics(all)

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

  • Cite this