TY - GEN

T1 - On locality-sensitive orderings and their applications

AU - Chan, Timothy M.

AU - Har-Peled, Sariel

AU - Jones, Mitchell

N1 - Funding Information:
Supported in part by NSF AF award CCF-1421231.
Publisher Copyright:
© Timothy M. Chan, Sariel Har-Peled, and Mitchell Jones.

PY - 2019/1/1

Y1 - 2019/1/1

N2 - 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.

AB - 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.

KW - Approximation algorithms

KW - Computational geometry

KW - Data structures

UR - http://www.scopus.com/inward/record.url?scp=85069494119&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85069494119&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.ITCS.2019.21

DO - 10.4230/LIPIcs.ITCS.2019.21

M3 - Conference contribution

AN - SCOPUS:85069494119

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 10th Innovations in Theoretical Computer Science, ITCS 2019

A2 - Blum, Avrim

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 10th Innovations in Theoretical Computer Science, ITCS 2019

Y2 - 10 January 2019 through 12 January 2019

ER -