Regresar

Map updates in a dynamic Voronoi data structure

Abstract:

In this paper we are using local and sequential map updates in the Voronoi data structure, which allows us to automatically record each event and performed map updates within the system. These map updates are executed through map construction commands that are composed of atomic actions (geometric algorithms for addition, deletion, and motion of spatial objects) on the dynamic Voronoi data structure. The formalization of map commands led to the development of a spatial language comprising a set of atomic operations or constructs on spatial primitives (points and lines), powerful enough to define the complex operations. This resulted in a new formal model for map updates, similar to "cellular encoding", where each update is uniquely characterized by the numbers of newly created and inactivated Voronoi regions. This research shows that the result of the formalization of the operations on the dynamic Voronoi data structure is a spatial language or a map grammar that is deterministic and reversible. © 2006 IEEE.