**Speaker:**
Serafino Cicerone
**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.