Subscribe: cs.CG updates on
Preview: cs.CG updates on

cs.CG updates on

Computer Science -- Computational Geometry (cs.CG) updates on the e-print archive

Published: 2018-02-22T20:30:00-05:00


Near Isometric Terminal Embeddings for Doubling Metrics. (arXiv:1802.07967v1 [cs.DS])

Given a metric space $(X,d)$, a set of terminals $K\subseteq X$, and a parameter $t\ge 1$, we consider metric structures (e.g., spanners, distance oracles, embedding into normed spaces) that preserve distances for all pairs in $K\times X$ up to a factor of $t$, and have small size (e.g. number of edges for spanners, dimension for embeddings). While such terminal (aka source-wise) metric structures are known to exist in several settings, no terminal spanner or embedding with distortion close to 1, i.e., $t=1+\epsilon$ for some small $0<\epsilon<1$, is currently known.

Here we devise such terminal metric structures for {\em doubling} metrics, and show that essentially any metric structure with distortion $1+\epsilon$ and size $s(|X|)$ has its terminal counterpart, with distortion $1+O(\epsilon)$ and size $s(|K|)+1$. In particular, for any doubling metric on $n$ points, a set of $k=o(n)$ terminals, and constant $0<\epsilon<1$, there exists:

(1) A spanner with stretch $1+\epsilon$ for pairs in $K\times X$, with $n+o(n)$ edges.

(2) A labeling scheme with stretch $1+\epsilon$ for pairs in $K\times X$, with label size $\approx \log k$.

(3) An embedding into $\ell_\infty^d$ with distortion $1+\epsilon$ for pairs in $K\times X$, where $d=O(\log k)$.

Moreover, surprisingly, the last two results apply if only $K$ is a doubling metric, while $X$ can be arbitrary.

Dynamic smooth compressed quadtrees (Fullversion). (arXiv:1712.05591v2 [cs.CG] UPDATED)

We introduce dynamic smooth (a.k.a. balanced) compressed quadtrees with worst-case constant time updates in constant dimensions. We distinguish two versions of the problem. First, we show that quadtrees as a space-division data structure can be made smooth and dynamic subject to split and merge operations on the quadtree cells. Second, we show that quadtrees used to store a set of points in $\mathbb{R}^d$ can be made smooth and dynamic subject to insertions and deletions of points. The second version uses the first but must additionally deal with compression and alignment of quadtree components. In both cases our updates take $2^{\mathcal{O}(d\log d )}$ time, except for the point location part in the second version which has a lower bound of $\Theta (\log n)$---but if a pointer (finger) to the correct quadtree cell is given, the rest of the updates take worst-case constant time. Our result implies that several classic and recent results (ranging from ray tracing to planar point location) in computational geometry which use quadtrees can deal with arbitrary point sets on a real RAM pointer machine.