Journal article
Kinetic Line Voronoi Operations and Their Reversibility
Geodesy, National Space Institute, Technical University of Denmark1
National Space Institute, Technical University of Denmark2
Image Analysis and Computer Graphics, Department of Informatics and Mathematical Modeling, Technical University of Denmark3
Department of Informatics and Mathematical Modeling, Technical University of Denmark4
University of Glamorgan5
Université Laval6
In Geographic Information Systems the reversibility of map update operations has not been explored yet. In this paper we are using the Voronoi based Quad-edge data structure to define reversible map update operations. The reversibility of the map operations has been formalised at the lowest level, as the basic algorithms for addition, deletion and moving of spatial objects.
Having developed reversible map operations on the lowest level, we were able to maintain reversibility of the map updates at higher levels as well. The reversibility in GIS can be used for efficient implementation of rollback mechanisms and dynamic map visualisations. In order to use the reversibility within the kinetic Voronoi diagram of points and open oriented line segments, we need to assure that reversing the map commands will produce exactly the changes in the map equivalent to the previous map states.
To prove that reversing the map update operations produces the exact reverse changes, we show an isomorphism between the set of complex operations on the kinetic Voronoi diagram of points and open oriented line segments and the sets of numbers of new / deleted Voronoi regions induced by these operations, and its explanation using the finite field of residual classes of integers modulo 5: F 5 = ℤ/5ℤ.
We show also an isomorphism between the set of complex operations on the kinetic Voronoi diagram of points and open oriented line segments and the set of differences of new and deleted Quad-Edge edges induced by these operations, and its explanation using the commutative ring ℤ15 = ℤ/15ℤ. We show finally the application of these theoretical results to the logging of a kinetic line Voronoi data structure. © 2010 Springer-Verlag.
Language: | English |
---|---|
Year: | 2010 |
Pages: | 139-165 |
ISSN: | 16113349 and 03029743 |
Types: | Journal article |
DOI: | 10.1007/978-3-642-16007-3_7 |
ORCIDs: | Anton, François |