Computing Reviews

Exploiting qualitative spatial reasoning for topological adjustment of spatial data
Wallgrün J.  SIGSPATIAL 2012 (Proceedings of the 20th International Conference on Advances in Geographic Information Systems, Redondo Beach, CA, Nov 6-9, 2012)229-238,2012.Type:Proceedings
Date Reviewed: 01/25/13

Suppose you have collected geographic information about a collection of objects and their positions. Their shapes are recorded accurately, but their positions may be misrecorded or misperceived. You additionally have information constraining the topological relations between the objects. For instance, you know that a building is entirely on an island and not leaking off of it, and you know that one end of a bridge is on the island and the other is on the mainland. Suppose that, due to the misrecorded positions of the objects, these constraints are not satisfied. The problem is finding the minimal number of repositionings for each object that will bring the system into a state where the constraints are satisfied.

The author of this paper developed a system that solves this problem for 2D convex objects with constraints stated in the region connection calculus (RCC) language known as RCC8. The system works by converting the problem into a mixed integer programming problem and then applying an existing solver for such problems.

The author further experimented with computing a transitive reduction of the constraint network (that is, a set-minimal subnetwork with the same solution space as the original network), and using the transitive reduction to generate the system of equations. Unsurprisingly, fewer equations were generated. More interestingly, the overall computation time decreased by a factor of more than two. There was no difference between using a simple greedy method for computing transitive reduction and using a more sophisticated method.

In the extensive literature on qualitative spatial reasoning using RCC8, there are surprisingly few papers that deal with generating geometric instantiations, so this paper is a welcome addition. However, the results here are very limited by considering only two dimensions, convex objects, and the translation of objects, and the techniques do not generalize in any obvious way.

Finally, there is a significant gap in the presentation. The experimentation was carried out over scenarios that were generated randomly. However, the paper does not say what random process was used. Since there is no standard probability distribution over polygons, and since the choice of random process can strongly affect the results of this kind of experiment, any paper that experimentally tests spatial computation using randomly generated instances should always specify the probability distribution or random process used.

Reviewer:  Ernest Davis Review #: CR140872 (1305-0416)

Reproduction in whole or in part without permission is prohibited.   Copyright 2024 ComputingReviews.com™
Terms of Use
| Privacy Policy