Map updates in a dynamic Voronoi data structure

Darka Mioc, Francesc/François Antón Castro, C. M. Gold, B. Moulin

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

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.
Original languageEnglish
Title of host publicationProceedings of the 3rd International Symposium on Voronoi Diagrams in Science and Engineering (ISVD’06)
Number of pages6
PublisherIEEE
Publication date2006
ISBN (Print)0-7695-2630-6
Publication statusPublished - 2006
Event3rd International Symposium on Voronoi Diagrams in Science and Engineering - Alberta, Canada
Duration: 2 Jul 20065 Jul 2006
Conference number: 3
http://pages.cpsc.ucalgary.ca/~marina/VD06/

Conference

Conference3rd International Symposium on Voronoi Diagrams in Science and Engineering
Number3
CountryCanada
CityAlberta
Period02/07/200605/07/2006
Internet address

Cite this

Mioc, D., Antón Castro, FF., Gold, C. M., & Moulin, B. (2006). Map updates in a dynamic Voronoi data structure. In Proceedings of the 3rd International Symposium on Voronoi Diagrams in Science and Engineering (ISVD’06) IEEE. http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4124829&tag=1