Product range spaces, sensitive sampling, and derandomization

Herve Bronnimann, Bernard Chazelle, Jiri Matousek

Research output: Chapter in Book/Report/Conference proceedingConference contribution

16 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. We derive a simpler optimal deterministic convex hull algorithm, and by extending the method to the intersection of a set of balls with the same radius, we obtain an O(n log3 n) deterministic algorithm for computing the diameter of an n-point set in 3-dimensional space.

Original languageEnglish (US)
Title of host publicationAnnual Symposium on Foundatons of Computer Science (Proceedings)
Editors Anon
PublisherPubl by IEEE
Pages400-409
Number of pages10
ISBN (Print)0818643706
StatePublished - Dec 1 1993
EventProceedings of the 34th Annual Symposium on Foundations of Computer Science - Palo Alto, CA, USA
Duration: Nov 3 1993Nov 5 1993

Other

OtherProceedings of the 34th Annual Symposium on Foundations of Computer Science
CityPalo Alto, CA, USA
Period11/3/9311/5/93

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture

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

Cite this