Relative (p, )-approximations in geometry

DOI10.1007/S00454-010-9248-1zbMATH Open1220.68106OpenAlexW2128227281MaRDI QIDQ633202FDOQ633202

Authors: 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

Recommendations

• On approximate halfspace range counting and relative epsilon-approximations
• Small-size relative ( p ,ε)-approximations for well-behaved range spaces
• Approximate halfspace range counting
• Approximations and optimal geometric divide-and-conquer
• Approximate Range Searching: The Absolute Model

zbMATH Keywords

range searchingrandom samplingepsilon 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)

Cites Work

• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• Sharper bounds for Gaussian and empirical processes
• \(\epsilon\)-nets and simplex range queries
• Almost tight bounds for \(\epsilon\)-nets
• Efficient partition trees
• Applications of random sampling in computational geometry. II
• Title not available (Why is that?)
• Random Sampling, Halfspace Range Reporting, and Construction of \lowercase$(\le k)$-Levels in Three Dimensions
• 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 for planar \(k\)-sets and related problems
• Optimal Search in Planar Subdivisions
• On levels in arrangements of lines, segments, planes, and triangles
• Discrepancy and approximations for bounded VC-dimension
• On Approximating the Depth and Related Problems
• Reporting points in halfspaces
• Quasi-optimal range searching in spaces of finite VC-dimension
• AN OPTIMAL ALGORITHM FOR COMPUTING (≤K)-LEVELS, WITH APPLICATIONS
• Decision theoretic generalizations of the PAC model for neural net and other learning applications
• More on k-sets of finite sets in the plane
• Relative \((p,\varepsilon )\)-approximations in geometry
• Randomized incremental constructions of three-dimensional convex hulls and planar voronoi diagrams, and approximate range counting
• Approximate halfspace range counting
• Improved bounds on the sample complexity of learning
• Range minima queries with respect to a random permutation, and approximate range counting
• The overlay of minimization diagrams in a randomized incremental construction
• Regression depth and center points.
• Ray shooting amid balls, farthest point from a line, and range emptiness searching
• Title not available (Why is that?)
• Product Range Spaces, Sensitive Sampling, and Derandomization
• On approximate range counting and depth
• Construction of \(\epsilon\)-nets

Cited In (31)

• Title not available (Why is that?)
• Geometric Packing under Nonuniform Constraints
• Digital almost nets
• Optimal approximations made easy
• Fast approximation of betweenness centrality through sampling
• Smallest k-enclosing rectangle revisited
• Turning Big Data Into Tiny Data: Constant-Size Coresets for $k$-Means, PCA, and Projective Clustering
• The VC dimension of metric balls under Fréchet and Hausdorff distances
• Nearly Optimal Planar $k$ Nearest Neighbors Queries under General Distance Functions
• Coresets for \((k, \ell ) \)-median clustering under the Fréchet distance
• On approximate halfspace range counting and relative epsilon-approximations
• Two proofs for shallow packings
• On ray shooting for triangles in 3-space and related problems
• Shape matching under rigid motion
• Smallest \(k\)-enclosing rectangle revisited
• On the approximation of Euclidean SL via geometric method
• Dynamic planar Voronoi diagrams for general distance functions and their algorithmic applications
• Subsampling in smoothed range spaces
• A Range Space with Constant VC Dimension for All-pairs Shortest Paths in Graphs
• Relative \((p,\varepsilon )\)-approximations in geometry
• Journey to the Center of the Point Set
• Union of random Minkowski sums and network vulnerability analysis
• A size-sensitive discrepancy bound for set systems of bounded primal shatter dimension
• Range minima queries with respect to a random permutation, and approximate range counting
• Title not available (Why is that?)
• Simplex Range Searching and Its Variants: A Review
• Improved dynamic geodesic nearest neighbor searching in a simple polygon
• Approximating the k-Level in Three-Dimensional Plane Arrangements
• Algorithms for ε-Approximations of Terrains
• Greedy Strategy Works for k-Center Clustering with Outliers and Coreset Construction
• Percolation centrality via Rademacher Complexity

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q633202)