Topological invariants of spatial databases (i.e., finite structures that capture the topological properties of the database) are receiving increasing attention since they can act as a basic structure to tackle relevant problems in the field (e.g., assessment of the topological equivalence). In this paper, the novel notion of boundary decomposition of a topological invariant is introduced and a polynomial time algorithm to compute such a decomposition is given. The decomposition consists of a recursive subdivision of the to- pological invariant into a finite set of simpler structures, each being a topological invariant in itself. The decomposition is proved to be lossless, a nice property which makes the boundary decomposition useful in real applications. 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 two-dimensional spatial data- bases.

A General Strategy for Decomposing Topological Invariants of Spatial Databases and an Application

CICERONE, SERAFINO;FRIGIONI, DANIELE;DI FELICE, Paolino
2002-01-01

Abstract

Topological invariants of spatial databases (i.e., finite structures that capture the topological properties of the database) are receiving increasing attention since they can act as a basic structure to tackle relevant problems in the field (e.g., assessment of the topological equivalence). In this paper, the novel notion of boundary decomposition of a topological invariant is introduced and a polynomial time algorithm to compute such a decomposition is given. The decomposition consists of a recursive subdivision of the to- pological invariant into a finite set of simpler structures, each being a topological invariant in itself. The decomposition is proved to be lossless, a nice property which makes the boundary decomposition useful in real applications. 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 two-dimensional spatial data- bases.
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

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/6872
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 3
social impact