Tree embedding has been a fundamental method in algorithm design with wide applications. We focus on the efficiency of building tree embedding in various computational settings under high-dimensional Euclidean \(\mathbb{R}^d\). We devise a new tree embedding construction framework that operates on an arbitrary metric decomposition with bounded diameter, offering a tradeoff between distortion and the locality of its algorithmic steps. This framework works for general metric spaces and may be of independent interest beyond the Euclidean setting. Using this framework, we obtain a dynamic algorithm that maintains an \(O_{\epsilon}(\log n)\)-distortion tree embedding with update time \(\tilde{O}(n^{\epsilon} + d)\) subject to point insertions/deletions, and a massively parallel algorithm that achieves \(O_{\epsilon}(\log n)\)-distortion in \(O(1)\) rounds and total space \(\tilde{O}(n^{1+\epsilon})\) (for constant \(\epsilon \in (0,1)\)). These new tree embedding results allow for a wide range of applications. Notably, under a similar performance guarantee as in our tree embedding algorithms, i.e., \(\tilde{O}(n^{\epsilon} + d)\) update time and \(O(1)\) rounds, we obtain \(O_{\epsilon}(\log n)\)-approximate dynamic and MPC algorithms for \(k\)-median and earth-mover distance in \(\mathbb{R}^d\).

We consider the Euclidean bi-chromatic matching problem in the dynamic setting, where the goal is to efficiently process point insertions and deletions while maintaining a high-quality solution. Computing the minimum cost bi-chromatic matching is one of the core problems in geometric optimization that has found many applications, most notably in estimating Wasserstein distance between two distributions. In this work, we present the first fully dynamic algorithm for Euclidean bi-chromatic matching with sublinear update time. For any fixed $\varepsilon > 0$, our algorithm achieves $O(1/\varepsilon)$-approximation and handles updates in $O(n^{\varepsilon})$ time. Our experiments show that our algorithm enables effective monitoring of the distributional drift in the Wasserstein distance on real and synthetic data sets, while outperforming the runtime of baseline approximations by orders of magnitudes.

We study the problem of computing Chamfer distance in the fully dynamic setting, where two sets of points $A, B \subset \mathbb{R}^{d}$, each of size up to $n$, dynamically evolve through point insertions or deletions and the goal is to efficiently maintain an approximation to $dist_{\mathrm{CH}}(A,B) = \sum_{a \in A} \min_{b \in B} dist(a,b)$, where $dist$ is a distance measure. Chamfer distance is a widely used dissimilarity metric for point clouds, with many practical applications that require repeated evaluation on dynamically changing datasets, e.g., when used as a loss function in machine learning. In this paper, we present the first dynamic algorithm for maintaining an approximation of the Chamfer distance under the $\ell_p$ norm for $p \in$ {$1,2$}. Our algorithm reduces to approximate nearest neighbor (ANN) search with little overhead. Plugging in standard ANN bounds, we obtain $(1+\epsilon)$-approximation in $\tilde{O}(\epsilon^{-d})$ update time and $O(1/\epsilon)$-approximation in $\tilde{O}(d n^{\epsilon^2} \epsilon^{-4})$ update time. We evaluate our method on real-world datasets and demonstrate that it performs competitively against natural baselines.