A simple and efficient kinetic spanner |
| |
Authors: | Mohammad Ali Abam Mark de Berg Joachim Gudmundsson |
| |
Institution: | aMADALGO, Department of Computing Science, University of Aarhus, Denmark;bDepartment of Computing Science, TU Eindhoven, The Netherlands;cNICTA, Sydney, Australia |
| |
Abstract: | We present a new and simple (1+ε)-spanner of size O(n/ε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/ε2) λs+2(n)), and at each event the spanner can be updated in O(1) time. |
| |
Keywords: | Kinetic data structures Geometric spanners |
本文献已被 ScienceDirect 等数据库收录! |
|