On locality-sensitive orderings and their applications

Research output: Contribution to journalArticlepeer-review

Abstract

For any constant d and parameter \varepsilon \in (0, 1/2], we show the existence of (roughly) 1/\varepsilon d orderings on the unit cube [0, 1)d such that for any two points p, q \in [0, 1)d close together under the Euclidean metric, there is a linear ordering in which all points between p and q in the ordering are ``close"" to p or q. More precisely, the only points that could lie between p and q in the ordering are points with Euclidean distance at most \varepsilon \| p - q\| from either p or q. These orderings are extensions of the Z-order, and they can be efficiently computed. Functionally, the orderings can be thought of as a replacement to quadtrees and related structures (like well-separated pair decompositions). We use such orderings to obtain surprisingly simple algorithms for a number of basic problems in low-dimensional computational geometry, including (i) dynamic approximate bichromatic closest pair, (ii) dynamic spanners, (iii) dynamic approximate minimum spanning trees, (iv) static and dynamic fault-tolerant spanners, and (v) approximate nearest neighbor search.

Original languageEnglish (US)
Pages (from-to)583-600
Number of pages18
JournalSIAM Journal on Computing
Volume49
Issue number3
DOIs
StatePublished - 2020

Keywords

  • Approximation algorithms
  • Computational geometry
  • Data structures

ASJC Scopus subject areas

  • Computer Science(all)
  • Mathematics(all)

Fingerprint Dive into the research topics of 'On locality-sensitive orderings and their applications'. Together they form a unique fingerprint.

Cite this