Relative \((p,\varepsilon )\)-approximations in geometry
From MaRDI portal
Publication:633202
DOI10.1007/s00454-010-9248-1zbMath1220.68106MaRDI QIDQ633202
Sariel Har-Peled, Micha Sharir
Publication date: 31 March 2011
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00454-010-9248-1
random sampling; range searching; epsilon nets; epsilon approximations; geometric discrepancy; relative approximations; spanning trees with low crossing number
68U05: Computer graphics; computational geometry (digital and algorithmic aspects)
65D18: Numerical aspects of computer graphics, image analysis, and computational geometry
Related Items
Geometric Packing under Nonuniform Constraints, Simplex Range Searching and Its Variants: A Review, Approximating the k-Level in Three-Dimensional Plane Arrangements, A Size-Sensitive Discrepancy Bound for Set Systems of Bounded Primal Shatter Dimension, Union of random Minkowski sums and network vulnerability analysis, Range minima queries with respect to a random permutation, and approximate range counting, Relative \((p,\varepsilon )\)-approximations in geometry, Two proofs for shallow packings, Fast approximation of betweenness centrality through sampling, Shape matching under rigid motion
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Range minima queries with respect to a random permutation, and approximate range counting
- Relative \((p,\varepsilon )\)-approximations in geometry
- The overlay of minimization diagrams in a randomized incremental construction
- Construction of \(\epsilon\)-nets
- More on k-sets of finite sets in the plane
- \(\epsilon\)-nets and simplex range queries
- Almost tight bounds for \(\epsilon\)-nets
- Reporting points in halfspaces
- Decision theoretic generalizations of the PAC model for neural net and other learning applications
- Efficient partition trees
- Discrepancy and approximations for bounded VC-dimension
- Sharper bounds for Gaussian and empirical processes
- On levels in arrangements of lines, segments, planes, and triangles
- Improved bounds for planar \(k\)-sets and related problems
- Applications of random sampling in computational geometry. II
- Quasi-optimal range searching in spaces of finite VC-dimension
- Regression depth and center points.
- Randomized incremental constructions of three-dimensional convex hulls and planar voronoi diagrams, and approximate range counting
- On Approximating the Depth and Related Problems
- Optimal Search in Planar Subdivisions
- Product Range Spaces, Sensitive Sampling, and Derandomization
- Random Sampling, Halfspace Range Reporting, and Construction of \lowercase$(\le k)$-Levels in Three Dimensions
- Approximate Halfspace Range Counting
- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
- AN OPTIMAL ALGORITHM FOR COMPUTING (≤K)-LEVELS, WITH APPLICATIONS
- On approximate range counting and depth
- Geometric discrepancy. An illustrated guide
- Using the Borsuk-Ulam theorem. Lectures on topological methods in combinatorics and geometry. Written in cooperation with Anders Björner and Günter M. Ziegler
- Improved bounds on the sample complexity of learning
