Topological invariants of spatial databases (i.e., finite structures that capture the topological properties of the database) have recently received increasing attention mainly in the framework of query languages. Actually, topological invariants can act as a basic structure to tackle relevant problems in the field. It turns out that the main concern in these problems is the manipulation of topological invariants by means of efficient algorithms. To this aim, we introduce the notion of "boundary decomposition" of a topological invariant, and give a polynomial time algorithm to compute such a decomposition. As a relevant application, we use the boundary decomposition as the basis for devising a polynomial time algorithm for testing the topological equivalence of two $2$-dimensional spatial databases. Other applications of the boundary decomposition are mentioned in the paper.

Decomposing Spatial Databases and Applications

CICERONE, SERAFINO;FRIGIONI, DANIELE;
2000-01-01

Abstract

Topological invariants of spatial databases (i.e., finite structures that capture the topological properties of the database) have recently received increasing attention mainly in the framework of query languages. Actually, topological invariants can act as a basic structure to tackle relevant problems in the field. It turns out that the main concern in these problems is the manipulation of topological invariants by means of efficient algorithms. To this aim, we introduce the notion of "boundary decomposition" of a topological invariant, and give a polynomial time algorithm to compute such a decomposition. As a relevant application, we use the boundary decomposition as the basis for devising a polynomial time algorithm for testing the topological equivalence of two $2$-dimensional spatial databases. Other applications of the boundary decomposition are mentioned in the paper.
0-7695-0680-1
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11697/36457
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 1
social impact