On Approximating the Depth and Related Problems
From MaRDI portal
Publication:3631896
DOI10.1137/060669474zbMath1180.68278MaRDI 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
68W40: Analysis of algorithms
68U05: Computer graphics; computational geometry (digital and algorithmic aspects)
68W25: Approximation algorithms
68W20: Randomized algorithms
Related Items
Matching Triangles and Basing Hardness on an Extremely Popular Conjecture, Simplex Range Searching and Its Variants: A Review, Unnamed Item, An efficient sum query algorithm for distance-based locally dominating functions, A Size-Sensitive Discrepancy Bound for Set Systems of Bounded Primal Shatter Dimension, The maximum box problem for moving points in the plane, Hardness of discrepancy computation and \(\varepsilon\)-net verification in high dimension, Minimizing the error of linear separators on linearly inseparable data, Approximating the Fréchet distance for realistic curves in near linear time, Union of random Minkowski sums and network vulnerability analysis, Lower bounds for the number of hyperplanes separating two finite sets of points, Limits of local search: quality and efficiency, Algorithms for marketing-mix optimization, 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, Preprocessing imprecise points for Delaunay triangulation: simplified and extended, A greedy clustering algorithm based on interval pattern concepts and the problem of optimal box positioning, Discrete Voronoi games and \(\epsilon\)-nets, in two and three dimensions, Covering many or few points with unit disks, Geometric pattern matching for point sets in the plane under similarity transformations, Enclosing weighted points with an almost-unit ball, The discrete Voronoi game in \(\mathbb{R}^2\), Building an optimal point-location structure in \(O(\operatorname{sort}(n))\) I/Os, Near-linear time approximation schemes for geometric maximum coverage, New exact algorithms for planar maximum covering location by ellipses problems, Robust fitting in computer vision: easy or hard?, An efficient sum query algorithm for distance-based locally dominating functions, Near-linear algorithms for geometric hitting sets and set covers, Near-linear approximation algorithms for geometric hitting sets, Solving some vector subset problems by Voronoi diagrams, Polynomial Time Algorithms for Bichromatic Problems, Delaunay Triangulation of Imprecise Points Simplified and Extended, Linear Time Approximation Schemes for Geometric Maximum Coverage
