Approximating minimization diagrams and generalized proximity search

Sariel Har-Peled, Nirman Kumar

Research output: Contribution to journalArticlepeer-review

Abstract

We investigate the classes of functions whose minimization diagrams can be approximated efficiently in ℝ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 multiplicatively weighted points, but the new technique also works for more general distance functions. For example, we get such data-structures for metrics induced by convex bodies, and the nearest furthest-neighbor distance to a set of point sets. Interestingly, our framework also works for distance functions that do not obey the triangle inequality. For many of these functions no near linear size approximation was known before.

Original languageEnglish (US)
Pages (from-to)944-974
Number of pages31
JournalSIAM Journal on Computing
Volume44
Issue number4
DOIs
StatePublished - 2015

Keywords

  • Approximation algorithms
  • Computational geometry
  • Data structures
  • Proximity search
  • Voronoi diagrams

ASJC Scopus subject areas

  • Computer Science(all)
  • Mathematics(all)

Fingerprint

Dive into the research topics of 'Approximating minimization diagrams and generalized proximity search'. Together they form a unique fingerprint.

Cite this