Kinetic spanners in Rd

ABSTRACT

We present a new (1+ε)-spanner for sets of n points in 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 the trajectories of the points can be described by bounded-degree polynomials, the number of topological changes to the spanner is O(n²/ε^d-1), and using a supporting data structure of size O(n log^dn) we can handle events in time O(log^d+1n). 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 R^d whose performance does not depend on the spread of the point set.

REFERENCES

• 1: Mohammad Ali Abam , Mark de Berg , Joachim Gudmundsson, A simple and efficient kinetic spanner, Proceedings of the twenty-fourth annual symposium on Computational geometry, June 09-11, 2008, College Park, MD, USA [doi>10.1145/1377676.1377729]
• 2: Mohammad Ali Abam , Mark de Berg , Bettina Speckmann, Kinetic KD-trees and longest-side KD-trees, Proceedings of the twenty-third annual symposium on Computational geometry, June 06-08, 2007, Gyeongju, South Korea [doi>10.1145/1247069.1247133]
• 3: Julien Basch , Leonidas J. Guibas, Data structures for mobile data, Journal of Algorithms, v.31 n.1, p.1-28, April 1999 [doi>10.1006/jagm.1998.0988]
• 4: Julien Basch , Leonidas J. Guibas , Li Zhang, Proximity problems on moving points, Proceedings of the thirteenth annual symposium on Computational geometry, p.344-351, June 04-06, 1997, Nice, France [doi>10.1145/262839.262998]
• 5: Mark de Berg , Otfried Cheong , Marc van Kreveld , Mark Overmars, Computational Geometry: Algorithms and Applications, Springer-Verlag TELOS, Santa Clara, CA, 2008
• 6: Mark de Berg , Joao Comba , Leonidas J. Guibas, A segment-tree based kinetic BSP, Proceedings of the seventeenth annual symposium on Computational geometry, p.134-140, June 2001, Medford, Massachusetts, United States [doi>10.1145/378583.378647]
• 7: Prosenjit Bose , Joachim Gudmundsson , Pat Morin, Ordered theta graphs, Computational Geometry: Theory and Applications, v.28 n.1, p.11-18, May 2004 [doi>10.1016/j.comgeo.2004.01.003]
• 8: P Chew, There is a planar graph almost as good as the complete graph, Proceedings of the second annual symposium on Computational geometry, p.169-177, June 02-04, 1986, Yorktown Heights, New York, United States [doi>10.1145/10515.10534]
• 9: K. Clarkson, Approximation algorithms for shortest path motion planning, Proceedings of the nineteenth annual ACM symposium on Theory of computing, p.56-65, January 1987, New York, New York, United States [doi>10.1145/28395.28402]
• 10: D. Eppstein. Spanning trees and spanners. In: J.-R. Sack and J. Urrutia (eds.), Handbook of Computational Geometry, Elsevier Science Publishers, pages 425--461, 2000.
• 11: Jie Gao , Leonidas J. Guibas , An Nguyen, Deformable spanners and applications, Computational Geometry: Theory and Applications, v.35 n.1, p.2-19, August 2006 [doi>10.1016/j.comgeo.2005.10.001]
• 12: Lee-Ad Gottlieb , Liam Roditty, Improved algorithms for fully dynamic geometric spanners and geometric routing, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.591-600, January 20-22, 2008, San Francisco, California
• 13: Lee-Ad Gottlieb , Liam Roditty, An Optimal Dynamic Spanner for Doubling Metric Spaces, Proceedings of the 16th annual European symposium on Algorithms, September 15-17, 2008, Karlsruhe, Germany [doi>10.1007/978-3-540-87744-8_40]
• 14: J. Gudmundsson and C. Knauer. Dilation and detour in geometric networks. In: T. Gonzalez (ed.), Handbook on approximation algorithms and metaheuristics. Chapter 52. Chapman & Hall/CRC, 2006.
• 15: Leonidas J. Guibas, Kinetic data structures: a state of the art report, Proceedings of the third workshop on the algorithmic foundations of robotics on Robotics : the algorithmic perspective: the algorithmic perspective, p.191-209, August 1998, Houston, Texas, United States
• 16: L. J. Guibas. Motion. In: J. Goodman and J. O'Rourke (eds.), Handbook of Discrete and Computational Geometry, pages 1117--1134. CRC Press, 2nd edition, 2004.
• 17: J. M. Keil, Approximating the complete Euclidean graph, No. 318 on SWAT 88: 1st Scandinavian workshop on algorithm theory, p.208-213, January 1988, Halmstad, Sweden
• 18: Kurt Mehlhorn, Data structures and algorithms 3: multi-dimensional searching and computational geometry, Springer-Verlag New York, Inc., New York, NY, 1984
• 19: Giri Narasimhan , Michiel Smid, Geometric Spanner Networks, Cambridge University Press, New York, NY, 2007
• 20: Liam Roditty, Fully dynamic geometric spanners, Proceedings of the twenty-third annual symposium on Computational geometry, June 06-08, 2007, Gyeongju, South Korea [doi>10.1145/1247069.1247134]
• 21: Micha Sharir , Pankaj K. Agarwal, Davenport-Schinzel sequences and their geometric applications, Cambridge University Press, New York, NY, 1996
• 22: J. Soares. Graph spanners: A survey. Congresus Numerantium, 89:225--238, 1992.
• 23: Dan E. Willard , George S. Lueker, Adding range restriction capability to dynamic data structures, Journal of the ACM (JACM), v.32 n.3, p.597-617, July 1985 [doi>10.1145/3828.3839]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

General Terms:
Algorithms, Theory

Keywords:
geometric spanners, kinetic data structures