Product range spaces, sensitive sampling, and derandomization

We introduce the concept of a {\em sensitive $\varepsilon$-approximation} and use it to derive a more efficient algorithm for computing $\varepsilon$-nets. We define and investigate product range spaces, for which we establish sampling theorems analogous to the standard finite VC-dimensional case. T...

Full description

Saved in:
Bibliographic Details
Published in:SIAM journal on computing 1999, Vol.28 (5), p.1552-1575
Main Authors: BRÖNNIMANN, H, CHAZELLE, B, MATOUSEK, J
Format: Article
Language:English
Subjects:
Algorithmics. Computability. Computer arithmetics
Algorithms
Applied mathematics
Applied sciences
Approximation
Computer science
Computer science
control theory
systems
Convex and discrete geometry
Exact sciences and technology
Geometry
Grants
Mathematics
Scholarships & fellowships
Sciences and techniques of general use
Theoretical computing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We introduce the concept of a {\em sensitive $\varepsilon$-approximation} and use it to derive a more efficient algorithm for computing $\varepsilon$-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 $\mbox{\smallBbb R}^d$. The algorithm is obtained by derandomization of a randomized incremental algorithm, and its running time of O(nlog n + n{\lfloor d/2\rfloor})$ is optimal for any fixed dimension $d\geq 2$.
ISSN:0097-5397
1095-7111
DOI:10.1137/S0097539796260321