Review of "Exploiting Qualitative Spatial Reasoning for Topological Adjustment of Spatial Data" by Jan Oliver Wallgrün, SIGSPATIAL GIS 2012. Review #CR140872, Computing Reviews,, Jan. 25, 2013.
Suppose that you have collected geographic information about a collection of objects and their positions. Their shapes are recorded accurately; however 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 it, and you know that one end of a bridge is on the island and the other is on the mainland. Due to the misrecorded positions of the objects, these constraints are not satisfied. The problem is to find the minimal repositionings for each object that will bring the system into a state where the constraints are satisfied.
The author developed a system that solves this problem for two-dimensional convex objects with constraints stated in the RCC8 language. 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 (i.e. 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 interesting, 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 large 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 --- two-dimensions, convex objects, only translation of objects considered --- and the techniques used 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 random 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.