On Approximating the Depth and Related Problems

DOI10.1137/060669474zbMATH Open1180.68278OpenAlexW2059541050MaRDI QIDQ3631896FDOQ3631896

Authors: Boris Aronov, Sariel Har-Peled 

Publication date: 22 June 2009

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/060669474

Recommendations

• On approximating the depth and related problems
• On approximate range counting and depth
• On approximate range counting and depth
• Approximating majority depth
• Algorithms for polytope covering and approximation

zbMATH Keywords

computational geometryrandomized algorithmsapproximation

Mathematics Subject Classification ID

Randomized algorithms (68W20) Analysis of algorithms (68W40) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Cited In (45)

• Polynomial time algorithms for bichromatic problems
• Hardness of discrepancy computation and \(\varepsilon\)-net verification in high dimension
• Algorithms for marketing-mix optimization
• The discrete Voronoi game in \(\mathbb{R}^2\)
• Covering many or few points with unit disks
• Building an optimal point-location structure in \(O(\operatorname{sort}(n))\) I/Os
• Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
• Minimizing the error of linear separators on linearly inseparable data
• Near-linear time approximation schemes for geometric maximum coverage
• A characterization of halfspace depth
• Delaunay Triangulation of Imprecise Points Simplified and Extended
• Edge estimation with independent set oracles
• A novel approximation algorithm for max-covering circle problem
• On the depth \(r\) Bernstein projector
• Approximating the Fréchet distance for realistic curves in near linear time
• New exact algorithms for planar maximum covering location by ellipses problems
• Geometric pattern matching for point sets in the plane under similarity transformations
• A lower bound for computing Oja depth
• Linear Time Approximation Schemes for Geometric Maximum Coverage
• Relative \((p,\varepsilon )\)-approximations in geometry
• The maximum box problem for moving points in the plane
• 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
• The overlay of minimization diagrams in a randomized incremental construction
• On approximate range counting and depth
• On approximate range counting and depth
• Preprocessing imprecise points for Delaunay triangulation: simplified and extended
• Lower bounds for the number of hyperplanes separating two finite sets of points
• Approximation algorithms for finding maximum containing circle and sphere
• Computation of depth in \(C(X)\)
• Solving some vector subset problems by Voronoi diagrams
• On Combinatorial Depth Measures
• Simplex Range Searching and Its Variants: A Review
• Near-linear algorithms for geometric hitting sets and set covers
• Approximating majority depth
• An efficient sum query algorithm for distance-based locally dominating functions
• Robust fitting in computer vision: easy or hard?
• An efficient sum query algorithm for distance-based locally dominating functions
• A greedy clustering algorithm based on interval pattern concepts and the problem of optimal box positioning
• On approximating the depth and related problems
• Discrete Voronoi games and \(\epsilon\)-nets, in two and three dimensions
• Enclosing weighted points with an almost-unit ball
• Limits of local search: quality and efficiency
• Near-linear approximation algorithms for geometric hitting sets

This page was built for publication: On Approximating the Depth and Related Problems

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