On Approximating the Depth and Related Problems

DOI10.1137/060669474zbMath1180.68278OpenAlexW2059541050MaRDI QIDQ3631896

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

zbMATH Keywords

approximationcomputational geometryrandomized algorithms

Mathematics Subject Classification ID

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

Related Items (34)

The discrete Voronoi game in \(\mathbb{R}^2\) ⋮ Matching Triangles and Basing Hardness on an Extremely Popular Conjecture ⋮ An efficient sum query algorithm for distance-based locally dominating functions ⋮ Covering many or few points with unit disks ⋮ Delaunay Triangulation of Imprecise Points Simplified and Extended ⋮ Linear Time Approximation Schemes for Geometric Maximum Coverage ⋮ Unnamed Item ⋮ The maximum box problem for moving points in the plane ⋮ Robust fitting in computer vision: easy or hard? ⋮ Hardness of discrepancy computation and \(\varepsilon\)-net verification in high dimension ⋮ Solving some vector subset problems by Voronoi diagrams ⋮ An efficient sum query algorithm for distance-based locally dominating functions ⋮ Range minima queries with respect to a random permutation, and approximate range counting ⋮ Near-linear approximation algorithms for geometric hitting sets ⋮ Minimizing the error of linear separators on linearly inseparable data ⋮ Relative \((p,\varepsilon )\)-approximations in geometry ⋮ The overlay of minimization diagrams in a randomized incremental construction ⋮ Simplex Range Searching and Its Variants: A Review ⋮ Polynomial Time Algorithms for Bichromatic Problems ⋮ Approximating the Fréchet distance for realistic curves in near linear time ⋮ Preprocessing imprecise points for Delaunay triangulation: simplified and extended ⋮ Union of random Minkowski sums and network vulnerability analysis ⋮ Lower bounds for the number of hyperplanes separating two finite sets of points ⋮ A greedy clustering algorithm based on interval pattern concepts and the problem of optimal box positioning ⋮ Building an optimal point-location structure in \(O(\operatorname{sort}(n))\) I/Os ⋮ Discrete Voronoi games and \(\epsilon\)-nets, in two and three dimensions ⋮ Near-linear time approximation schemes for geometric maximum coverage ⋮ Limits of local search: quality and efficiency ⋮ A Size-Sensitive Discrepancy Bound for Set Systems of Bounded Primal Shatter Dimension ⋮ Algorithms for marketing-mix optimization ⋮ Geometric pattern matching for point sets in the plane under similarity transformations ⋮ Enclosing weighted points with an almost-unit ball ⋮ New exact algorithms for planar maximum covering location by ellipses problems ⋮ Near-linear algorithms for geometric hitting sets and set covers

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