Reductions among high dimensional proximity problems

MaRDI QIDQ2768379zbMATH OpenFDO

Authors Ashish Goel, Piotr Indyk, Kasturi Varadarajan

Publication date 24 March 2002

zbMATH Keywords

approximate bottleneck matchingapproximate diameterapproximate discrete centerapproximate furthest neighboursapproximate metric facility locationapproximate minimum weight matchinghigh dimensional proximity problemsnearest neighbour queriessubquadratic running time

Mathematics Subject Classification ID

Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Recommendations

• scientific article; zbMATH DE number 1445325
• Approximate closest-point queries in high dimensions
• Automata, Languages and Programming
• scientific article; zbMATH DE number 1775450
• Reporting neighbors in high-dimensional Euclidean space

Cited in

(21)

• No dimension-independent core-sets for containment under homothetics
• High-dimensional approximate \(r\)-nets
• Uncertainty quantification of the 4th kind; optimal posterior accuracy-uncertainty tradeoff with the minimum enclosing ball
• A branch-and-bound method for the minimum \(k\)-enclosing ball problem
• An \(O(\log n)\) query time algorithm for reducing \(\varepsilon \)-NN to \((c,r)\)-NN
• Streaming algorithms for extent problems in high dimensions
• An efficient algorithm for the smallest enclosing ball problem in high dimensions
• Optimal core-sets for balls
• Space exploration via proximity search
• Proximity algorithms for nearly-doubling spaces
• scientific article; zbMATH DE number 2079383 (Why is no real title available?)
• On the difference between closest, furthest, and orthogonal pairs: nearly-linear vs barely-subquadratic complexity
• scientific article; zbMATH DE number 1445325 (Why is no real title available?)
• Probabilistic smallest enclosing ball in high dimensions via subgradient sampling
• Proximity algorithms for nearly doubling spaces
• Approximate minimum enclosing balls in high dimensions using core-sets
• Energy-efficient paths in radio networks
• Parameterized approximation algorithms and lower bounds for k-center clustering and variants
• A coreset for approximate furthest-neighbor queries in a simple polygon
• Streaming diameter of high-dimensional points
• Efficient approximation algorithms for clustering point-sets

This page was built for publication: Reductions among high dimensional proximity problems

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