Approximating Minimization Diagrams and Generalized Proximity Search

DOI10.1137/140959067zbMATH Open1337.68270arXiv1304.0393OpenAlexW2174417008MaRDI QIDQ5502175FDOQ5502175

Sariel Har-Peled, Nirman Kumar

Publication date: 18 August 2015

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

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.

Full work available at URL: https://arxiv.org/abs/1304.0393

zbMATH Keywords

computational geometrydata structuresapproximation algorithmsVoronoi diagramsproximity search

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Data structures (68P05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• An optimal algorithm for approximate nearest neighbor searching fixed dimensions
• Efficient partition trees
• Algorithms in real algebraic geometry
• Approximate nearest neighbor: towards removing the curse of dimensionality
• Nearest-Neighbor Searching Under Uncertainty II
• Point location in arrangements of hyperplanes
• Managing and mining uncertain data
• A decomposition of multidimensional point sets with applications to k -nearest-neighbors and n -body potential fields
• A Randomized Algorithm for Closest-Point Queries
• Optimal partition trees
• Ray Shooting and Parametric Search
• Nearest-neighbor searching under uncertainty. I
• Constructing Approximate Shortest Path Maps in Three Dimensions
• Approximating Minimization Diagrams and Generalized Proximity Search
• New lower bounds for Hopcroft's problem
• Space-time tradeoffs for approximate nearest neighbor searching

Cited In (6)

• Batched Point Location in SINR Diagrams via Algebraic Tools
• 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

Recommendations

• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Proximity search for 0--1 mixed-integer convex programming 👍 👎
• Approximate Local Search in Combinatorial Optimization 👍 👎
• Approximation algorithms for minimum norm and ordered optimization problems 👍 👎
• Minimax Parametric Optimization Problems and Multidimensional Parametric Searching 👍 👎
• A proximal point algorithm for minimax problems 👍 👎
• Approximate search for a global minimum in problems of mathematical programming that are close to convex 👍 👎
• Approximation Algorithms for Min-Max Generalization Problems 👍 👎
• Approximation Algorithms for Min-Max Generalization Problems 👍 👎

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)