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.
Friday, September 28, 2007
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment