Relative \((p,\varepsilon )\)-approximations in geometry

DOI10.1007/s00454-010-9248-1zbMath1220.68106OpenAlexW2128227281MaRDI 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

zbMATH Keywords

random samplingrange searchingepsilon netsepsilon approximationsgeometric discrepancyrelative approximationsspanning trees with low crossing number

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Related Items (27)

Optimal approximations made easy ⋮ Journey to the Center of the Point Set ⋮ The VC dimension of metric balls under Fréchet and Hausdorff distances ⋮ On Ray Shooting for Triangles in 3-Space and Related Problems ⋮ A Range Space with Constant VC Dimension for All-pairs Shortest Paths in Graphs ⋮ Geometric Packing under Nonuniform Constraints ⋮ Coresets for \((k, \ell ) \)-median clustering under the Fréchet distance ⋮ Range minima queries with respect to a random permutation, and approximate range counting ⋮ Relative \((p,\varepsilon )\)-approximations in geometry ⋮ Simplex Range Searching and Its Variants: A Review ⋮ Approximating the k-Level in Three-Dimensional Plane Arrangements ⋮ Shape matching under rigid motion ⋮ Dynamic planar Voronoi diagrams for general distance functions and their algorithmic applications ⋮ Union of random Minkowski sums and network vulnerability analysis ⋮ Turning Big Data Into Tiny Data: Constant-Size Coresets for $k$-Means, PCA, and Projective Clustering ⋮ Fast approximation of betweenness centrality through sampling ⋮ A Size-Sensitive Discrepancy Bound for Set Systems of Bounded Primal Shatter Dimension ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Two proofs for shallow packings ⋮ Smallest \(k\)-enclosing rectangle revisited ⋮ Greedy Strategy Works for k-Center Clustering with Outliers and Coreset Construction ⋮ Unnamed Item ⋮ Smallest k-enclosing rectangle revisited ⋮ Percolation centrality via Rademacher Complexity ⋮ Nearly Optimal Planar $k$ Nearest Neighbors Queries under General Distance Functions ⋮ Digital almost nets

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

This page was built for publication: Relative \((p,\varepsilon )\)-approximations in geometry