id: 05903702
dt: j
an: 05903702
au: Abam, Mohammad Ali; de Berg, Mark
ti: Kinetic spanners in $\Bbb R^{d}$.
so: Discrete Comput. Geom. 45, No. 4, 723-736 (2011).
py: 2011
pu: Springer-Verlag, New York, NY
la: EN
cc: 
ut: geometric spanners; kinetic data structures
ci: 
li: doi:10.1007/s00454-011-9343-y
ab: Summary: We present a new $(1+ε)$-spanner for sets of $n$ points in $\Bbb
    R^{d}$. Our spanner has size $O(n / ϵ^{d-1})$ and maximum degree
    $O(\log ^{d} n)$. The main advantage of our spanner is that it can be
    maintained efficiently as the points move: Assuming that the
    trajectories of the points can be described by bounded-degree
    polynomials, the number of topological changes to the spanner is
    $O(n^{2} / ε^{d-1})$, and using a supporting data structure of size
    $O(n \log^{d} n)$, we can handle events in time $O(\log ^{d+1} n)$.
    Moreover, the spanner can be updated in time $O(\log n)$ if the flight
    plan of a point changes. This is the first kinetic spanner for points
    in $\Bbb R^{d}$ whose performance does not depend on the spread of the
    point set.
rv: