Dynamic Locality Sensitive Orderings in Doubling Metrics

In their pioneering work, Chan, Har-Peled, and Jones (SICOMP 2020) introduced locality-sensitive ordering (LSO), and constructed an LSO with a constant number of orderings for point sets in the d-dimensional Euclidean space. Furthermore, their LSO could be made dynamic effortlessly under point insertions and deletions, taking O(log(n)) time per update by exploiting Euclidean geometry. Their LSO provides a powerful primitive to solve a host of geometric problems in Euclidean spaces in both dynamic and static settings. Filtser and Le (STOC 2022) constructed the first LSO with a constant number of orderings in the more general setting of doubling metrics. However, their algorithm is inherently static since it relies on several sophisticated constructions in intermediate steps, none of which is known to have a dynamic version. Making their LSO dynamic would recover the full generality of LSO and provide a general tool to dynamize a vast number of static constructions in doubling metrics. In this work, we give a dynamic algorithm that has O(log n) time per update for constructing an LSO in doubling metrics under point insertions and deletions. To this end, we introduce a toolkit of several new data structures: a pairwise index tree (PIT) which augments the standard net tree with the pairwise property, a pairwise tree cover which in a certain sense is a tree counterpart of LSO, a net tree cover for stabilizing the net tree, and a leaf tracker for keeping track of a DFS ordering of leaves in a dynamic tree. A key technical problem that we solves in this work is stabilizing the dynamic net tree of Cole and Gottlieb (STOC 2006), a central dynamic data structure in doubling metrics, using a dynamic net tree cover. Specifically, we show that every update to the dynamic net tree can be decomposed into a few very simple updates to trees in the net tree cover. As stability is the key to any dynamic algorithm, our technique could be useful for other problems in doubling metrics. We obtain several algorithmic applications from our dynamic LSO, including dynamic fault-tolerant spanner, dynamic tree cover, dynamic nearest neighbor search with optimal search time, dynamic (bichromatic) closest pair of points, all in doubling metrics. Most notably, we obtain the first dynamic algorithm for maintaining an k-fault tolerant spanner in doubling metrics with optimal sparsity in optimal O(log n) time per update.