Product Range Spaces, Sensitive Sampling, and Derandomization
Authors:
- Hervé BrönnimannHBHervé Brönnimann
- Bernard ChazelleBCBernard Chazelle
- Jiri MatousekJMJiri Matousek
- 1 January 1999
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 28 (5) , 1552-1575
Abstract
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$.
Keywords
This publication has 21 references indexed in Scilit:
- On Linear-Time Deterministic Algorithms for Optimization Problems in Fixed DimensionJournal of Algorithms, 1996
- Improved bounds on weak ε-nets for convex setsDiscrete & Computational Geometry, 1995
- An optimal convex hull algorithm in any fixed dimensionDiscrete & Computational Geometry, 1993
- Cutting hyperplanes for divide-and-conquerDiscrete & Computational Geometry, 1993
- A deterministic view of random sampling and its use in geometryCombinatorica, 1990
- Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithmsACM Transactions on Graphics, 1990
- Applications of random sampling in computational geometry, IIDiscrete & Computational Geometry, 1989
- A Randomized Algorithm for Closest-Point QueriesSIAM Journal on Computing, 1988
- Algorithms in Combinatorial Geometry1987
- Some special vapnik-chervonenkis classesDiscrete Mathematics, 1981