Title: "On the computational complexity of topological equivalence of spatial databases"
Abstract. In this talk we give an answer to an open problem posed by Paredaens in 1995, i.e., determining the time complexity required to test the topological equivalence of two 2-dimensional spatial databases. Intuitively, two spatial databases are topologically equivalent if their topological properties do not change as a consequence of topological transformations (as for instance, homeomorphisms or isotopies). We provide an algorithm that, given two 2-dimensional spatial databases A and B, decides whether A and B are topologically equivalent with respect to isotopies. The time complexity of the algorithm is polynomial in the size of the databases. Up to now, it was only known that testing the topological equivalence of two 2-dimensional spatial databases is decidable. Three main ingredients have been used: the notion of topological invariant of a spatial database, that is, a classical finite structure that captures exactly the topological properties of the database up to isotopies; the result that two spatial databases are topologically equivalent with respect to isotopies if and only if the corresponding topological invariants are isomorphic; the notion of boundary decomposition of the topological invariant. The first two ingredients are known from the literature, the last one is new. Using the above ingredients, our algorithm is able to return in polynomial time all possible isomorphisms between the topological invariants of A and B. This result induces all the isotopies and homeomorphisms between A and B.