Topological canonization of planar spatial data and its incremental maintenance

Abstract

It is known that to a planar spatial database, represented by a Semi-algebraic set in the plane, one can associate a structure, here called the “topological canonization”, such that two databases are topologically equivalent if and only if their topological canonizations are isomorphic. The advantage of a topological canonization is that it contains precisely the information one needs if one is only interested in topological properties of the spatial data. In this paper we represent semi-algebraic sets using plane graph structures. Canonizations are represented by plane graph structures as well (the so-called canonical structures). We discuss the basic properties of canonical structures and of canonization. We then present a method for incremental maintenance of the canonization under elementary updates on the original spatial database. Incremental maintenance takes less time than recomputing the canonization from scratch.