Reversibility of the Quad-Edge operations in the Voronoi data structure

Darka Mioc, François Anton, Christopher Gold, Bernard Moulin

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

    327 Downloads (Pure)

    Abstract

    In Geographic Information Systems the reversibility of map update operations have 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 have been formalised at the lowest level, as the basic algorithms for addition, dele- tion and moving of spatial objects. Having developed re- versible map operations on the lowest level, we were able to maintain reversibility of the map updates at higher level as well. The reversibility in GIS can be used for efficient implementation of rollback mechanisms and dynamic map visualisations.
    Original languageEnglish
    Title of host publicationInternational Symposium on Voronoi Diagrams in Science and Engineering (ISVD)
    PublisherIEEE
    Publication date2007
    Pages135-144
    ISBN (Print)9780769528694
    DOIs
    Publication statusPublished - 2007
    Event4th International Symposium on Voronoi Diagrams in Science and Engineering - Glamorgan University, Pontypridd, United Kingdom
    Duration: 9 Jul 200711 Jul 2007
    Conference number: 2007
    http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=4276089

    Conference

    Conference4th International Symposium on Voronoi Diagrams in Science and Engineering
    Number2007
    LocationGlamorgan University
    CountryUnited Kingdom
    CityPontypridd
    Period09/07/200711/07/2007
    Internet address

    Keywords

    • Voronoi diagram of circles, Delaunay graph of circles, Gröbner basis, eigenvalues

    Fingerprint Dive into the research topics of 'Reversibility of the Quad-Edge operations in the Voronoi data structure'. Together they form a unique fingerprint.

    Cite this