Friday, September 28, 2007

Kinetic spanners

Today and tomorow I'm in Eindhoven. I spent most of the day working together with Mark de Berg and Mohammad Abam on the problem of constructing kinetic spanners. That is, given a set of moving points in the plane can we maintain a t-spanner with a small number of topological changes, for a given constant t>1.

Previous work on this problem includes a paper by Karavelas and Guibas (SODA'01) and a paper by Agarwal, Wang and Yu (SoCG'04). Agarwal et al. show that a triangulation (the Delauany triangulation is known to have small dilation) can be maintained with n^2 * 2^{\sqrt{\log n \loglog n}} topological updates, if the trajectories of the input points are algebraic curves of fixed degree. We hope to be able to prove similar results for t-spanners.

We looked at this problem before but this time we were lucky to obtain some initial results so I'm looking forward to continue the discussion tomorrow.

No comments:

Post a Comment