Personal tools
You are here: Home CG seminar 2019 On Locality-Sensitive Orderings and Their Applications
« February 2019 »
Log in

Forgot your password?

On Locality-Sensitive Orderings and Their Applications

Wednesday, January 2nd, 2019, 16:10

Schreiber 309


On Locality-Sensitive Orderings and Their Applications

Sariel Har-Peled, UIUC


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.


Joint work with Timothy M. Chan and Mitchell Jones

Document Actions