Chan, Timothy M. ;
HarPeled, Sariel ;
Jones, Mitchell
On LocalitySensitive Orderings and Their Applications
Abstract
For any constant d and parameter epsilon > 0, we show the existence of (roughly) 1/epsilon^d orderings on the unit cube [0,1)^d, such that any two points p, q in [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 epsilon  p  q  from p or q. These orderings are extensions of the Zorder, and they can be efficiently computed.
Functionally, the orderings can be thought of as a replacement to quadtrees and related structures (like wellseparated pair decompositions). We use such orderings to obtain surprisingly simple algorithms for a number of basic problems in lowdimensional computational geometry, including (i) dynamic approximate bichromatic closest pair, (ii) dynamic spanners, (iii) dynamic approximate minimum spanning trees, (iv) static and dynamic faulttolerant spanners, and (v) approximate nearest neighbor search.
BibTeX  Entry
@InProceedings{chan_et_al:LIPIcs:2018:10114,
author = {Timothy M. Chan and Sariel HarPeled and Mitchell Jones},
title = {{On LocalitySensitive Orderings and Their Applications}},
booktitle = {10th Innovations in Theoretical Computer Science Conference (ITCS 2019)},
pages = {21:121:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770958},
ISSN = {18688969},
year = {2018},
volume = {124},
editor = {Avrim Blum},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/10114},
URN = {urn:nbn:de:0030drops101140},
doi = {10.4230/LIPIcs.ITCS.2019.21},
annote = {Keywords: Approximation algorithms, Data structures, Computational geometry}
}
2018
Keywords: 

Approximation algorithms, Data structures, Computational geometry 
Seminar: 

10th Innovations in Theoretical Computer Science Conference (ITCS 2019)

Issue date: 

2018 
Date of publication: 

2018 