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 language | English (US) |
---|---|
Title of host publication | Annual Symposium on Foundatons of Computer Science (Proceedings) |
Editors | Anon |
Publisher | Publ by IEEE |
Pages | 400-409 |
Number of pages | 10 |
ISBN (Print) | 0818643706 |
State | Published - Dec 1 1993 |
Event | Proceedings of the 34th Annual Symposium on Foundations of Computer Science - Palo Alto, CA, USA Duration: Nov 3 1993 → Nov 5 1993 |
Other
Other | Proceedings of the 34th Annual Symposium on Foundations of Computer Science |
---|---|
City | Palo Alto, CA, USA |
Period | 11/3/93 → 11/5/93 |
All Science Journal Classification (ASJC) codes
- Hardware and Architecture