Robustness of Spatial Relation Evaluation

In the last few years the amount of spatial data available through the network has increased both in volume and in heterogeneity, so that dealing with this huge amount of information has become an interesting new research challenge. In particular, spatial data is usually represented through a vector model upon which several spatial relations have been defined. Such relations represent the basic tools for querying spatial data and their robust evaluation in a distributed heterogeneous environment is an important issue to consider, in order to allow an effective usage of this kind of data. Among all possible spatial relations, this report considers the topological ones, since they are the most widely available in existing systems and represent the building blocks for the implementation of other spatial relations. The conditions and the operations needed to make a dataset robust w.r.t. topological interpretations strictly depends on the adopted evaluation model. In particular, this report considers an environment where two different eval- uation models for topological relations exist, one in which equality is based on identity of geometric primitives, and the other one where a tolerance in equality evaluation is introduced. Given such premises, the report proposes a set of rules for guaranteeing the robustness in both models, and discusses the applicability of available algorithms of the Snap Rounding family, in order to preserve robustness in case of perturbations.