@inproceedings{7ca274dc10bf46aa97a4870382ad127e,

title = "Product range spaces, sensitive sampling, and derandomization",

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.",

author = "Herve Bronnimann and Bernard Chazelle and Jiri Matousek",

year = "1993",

language = "English (US)",

isbn = "0818643706",

series = "Annual Symposium on Foundatons of Computer Science (Proceedings)",

publisher = "Publ by IEEE",

pages = "400--409",

editor = "Anon",

booktitle = "Annual Symposium on Foundatons of Computer Science (Proceedings)",

note = "Proceedings of the 34th Annual Symposium on Foundations of Computer Science ; Conference date: 03-11-1993 Through 05-11-1993",

}