Product Range Spaces, Sensitive Sampling, and Derandomization

We introduce the concept of a sensitive /spl epsi/-approximation, and use it to derive a more efficient algorithm for computing /spl epsi/-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(nlog/sup 3/ n) deterministic algorithm for computing the diameter of an n-point set in 3-dimensional space. >

Authors

• Hervé Brönnimann
• Bernard Chazelle
• Jirí Matousek 0001

Keywords

• Sampling methods
• Computer science
• Mathematics
• Geometry
• US Department of Energy
• Polynomials
• Deterministic
• Convex Hull
• Sampling Theorem
• Simplex
• Local Point
• Line Segment
• Set Of Cells
• Correction Algorithm
• Convex Set
• Binary Search
• Polytope
• N Log N
• Spherical Case