On locality-sensitive orderings and their applications

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

Abstract

For any constant d and parameter ε > 0, we show the existence of (roughly) 1/εd orderings on the unit cube [0, 1)d, such that any two points p, q ∈ [0, 1)d that are close together under the Euclidean metric are “close together” in one of these linear orderings in the following sense: the only points that could lie between p and q in the ordering are points with Euclidean distance at most ε‖p − q‖ from 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)
Title of host publication10th Innovations in Theoretical Computer Science, ITCS 2019
EditorsAvrim Blum
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959770958
DOIs
StatePublished - Jan 1 2019
Event10th Innovations in Theoretical Computer Science, ITCS 2019 - San Diego, United States
Duration: Jan 10 2019Jan 12 2019

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume124
ISSN (Print)1868-8969

Conference

Conference10th Innovations in Theoretical Computer Science, ITCS 2019
Country/TerritoryUnited States
CitySan Diego
Period1/10/191/12/19

Keywords

  • Approximation algorithms
  • Computational geometry
  • Data structures

ASJC Scopus subject areas

  • Software

Fingerprint

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

Cite this