Establishing Robustness of a Spatial Dataset in a Tolerance-Based Vector Model

Spatial data are usually described through a vector model in which geometries are rep- resented by a set of coordinates embedded into an Euclidean space. The use of a finite representation, instead of the real numbers theoretically required, causes many robustness problems which are well-known in literature. Such problems are made even worst in a distributed context, where data is exchanged between different systems and several perturbations can be introduced in the data representation. In this context, a spatial dataset is said to be robust if the evaluation of the spatial relations existing among its objects can be performed in different systems, producing always the same result.In order to discuss the robustness of a spatial dataset, two implementation models have to be distinguished, since they determine different ways to evaluate the relations existing among geometric objects: the identity and the tolerance model. The robustness of a dataset in the identity model has been widely discussed in [Belussi et al., 2012, Belussi et al., 2013, Belussi et al., 2015a] and some algorithms of the Snap Rounding (SR) family [Hobby, 1999, Halperin and Packer, 2002, Packer, 2008, Belussi et al., 2015b] can be successfully applied in such context. Conversely, this problem has been less explored in the tolerance model. The aim of this paper is to propose an algorithm inspired by the ones of SR family for establishing or restoring the robustness of a vector dataset in the tolerance model. The main ideas are to introduce an additional operation which spreads instead of snapping geometries, in order to preserve the original relation between them, and to use a tolerance region for such operation instead of a single snapping location. Finally, some experiments on real-world datasets are presented, which confirms how the proposed algorithm can establish the robustness of a dataset.