TY - GEN
T1 - On locality-sensitive orderings and their applications
AU - Chan, Timothy M.
AU - Har-Peled, Sariel
AU - Jones, Mitchell
N1 - 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 -