Approximating minimization diagrams and generalized proximity search

Sariel Har-Peled, Nirman Kumar

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We investigate the classes of functions whose minimization diagrams can be approximated efficiently in IRd. We present a general framework and a data-structure that can be used to approximate theminimization 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 obey the triangle inequality. For many of these functions no near-linear size approximation was known before.

Original languageEnglish (US)
Title of host publicationProceedings - 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013
Pages717-726
Number of pages10
DOIs
StatePublished - 2013
Event2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013 - Berkeley, CA, United States
Duration: Oct 27 2013Oct 29 2013

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
ISSN (Print)0272-5428

Other

Other2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013
Country/TerritoryUnited States
CityBerkeley, CA
Period10/27/1310/29/13

ASJC Scopus subject areas

  • General Computer Science

Fingerprint

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

Cite this