A simple and efficient kinetic spanner

作者：Abam Mohammad Ali; de Berg Mark^*; Gudmundsson Joachim

来源：Computational Geometry-Theory and Applications, 2010, 43(3): 251-256.

DOI：10.1016/j.comgeo.2009.01.008

• Kinetic data structures
• Geometric spanners

We present a new and simple (1 + epsilon)-spanner of size O (n/epsilon(2)) for a set of n points in the plane, which can be maintained efficiently as the points move. Assuming the trajectories of the points can be described by polynomials whose degrees are at most s, the number of topological changes to the spanner is O((n/epsilon(2)) . lambda(s+2) (n)), and at each event the spanner can be updated in O(1) time.

• 出版日期2010-4