Kinetic spanners in Rd

M.A. Abam, M.T. Berg, de

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

14 Citaten (Scopus)
52 Downloads (Pure)


We present a new $(1 + \epsilon)$-spanner for sets of $n$ points in $\mathbb{R}^d$. Our spanner has size $O(n/\epsilon^{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/\epsilon^{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 $\mathbb{R}^d$ whose performance does not depend on the spread of the point set.
Originele taal-2Engels
Pagina's (van-tot)723-736
TijdschriftDiscrete and Computational Geometry
Nummer van het tijdschrift4
StatusGepubliceerd - 2011

Vingerafdruk Duik in de onderzoeksthema's van 'Kinetic spanners in Rd'. Samen vormen ze een unieke vingerafdruk.

Citeer dit