Approximating Minimization Diagrams and Generalized Proximity Search
From MaRDI portal
Publication:5502175
Abstract: We investigate the classes of functions whose minimization diagrams can be approximated efficiently in Re^d. We present a general framework and a data-structure that can be used to approximate the minimization diagram of such functions. The resulting data-structure has near linear size and can answer queries in logarithmic time. Applications include approximating the Voronoi diagram of (additively or multiplicatively) weighted points. Our technique also works for more general distance functions, such as metrics induced by convex bodies, and the nearest furthest-neighbor distance to a set of point sets. Interestingly, our framework works also for distance functions that do not comply with the triangle inequality. For many of these functions no near-linear size approximation was known before.
Recommendations
- Approximate local search in combinatorial optimization
- Approximate Local Search in Combinatorial Optimization
- Approximation algorithms for min-max generalization problems
- Approximation algorithms for min-max generalization problems
- Approximate search for a global minimum in problems of mathematical programming that are close to convex
- Approximation algorithms for min-distance problems
- A proximal point algorithm for minimax problems
- Approximation algorithms for minimum norm and ordered optimization problems
- Proximity search for 0--1 mixed-integer convex programming
- Minimax Parametric Optimization Problems and Multidimensional Parametric Searching
Cites work
- scientific article; zbMATH DE number 5506204 (Why is no real title available?)
- scientific article; zbMATH DE number 732977 (Why is no real title available?)
- scientific article; zbMATH DE number 1775450 (Why is no real title available?)
- scientific article; zbMATH DE number 2119656 (Why is no real title available?)
- A Randomized Algorithm for Closest-Point Queries
- A decomposition of multidimensional point sets with applications to k -nearest-neighbors and n -body potential fields
- Algorithms in real algebraic geometry
- An optimal algorithm for approximate nearest neighbor searching fixed dimensions
- Approximate nearest neighbor: towards removing the curse of dimensionality
- Approximating Minimization Diagrams and Generalized Proximity Search
- Computational geometry. Algorithms and applications.
- Constructing Approximate Shortest Path Maps in Three Dimensions
- Efficient partition trees
- Geometric approximation algorithms
- Managing and mining uncertain data
- Nearest-neighbor searching under uncertainty. I
- Nearest-neighbor searching under uncertainty. II
- New lower bounds for Hopcroft's problem
- Optimal partition trees
- Point location in arrangements of hyperplanes
- Ray Shooting and Parametric Search
- Space-time tradeoffs for approximate nearest neighbor searching
Cited in
(6)- Sensitivity analysis and tailored design of minimization diagrams
- The overlay of minimization diagrams in a randomized incremental construction
- Approximating Minimization Diagrams and Generalized Proximity Search
- Resolving SINR Queries in a Dynamic Setting
- Robust proximity search for balls using sublinear space
- Approximate nearest neighbor search for \(\ell_{p}\)-spaces \((2 < p < \infty)\) via embeddings
This page was built for publication: Approximating Minimization Diagrams and Generalized Proximity Search
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5502175)
