Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
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: Jan 25 2013

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)
Bookmark and Share
  Reviewer Selected
Featured Reviewer
Relation Systems (I.2.4 ... )
Constrained Optimization (G.1.6 ... )
Would you recommend this review?
Other reviews under "Relation Systems": Date
Case-based reasoning
Kolodner J., Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993. Type: Book (9781558602373)
Oct 1 1995
On the logical foundations of compound predicate formulae for legal knowledge representation
Yoshino H. Artificial Intelligence and Law 5(1/2): 77-96, 1997. Type: Article
May 1 1999
Deduction Graphs: An Algorithm and Applications
Yang C. IEEE Transactions on Software Engineering 15(1): 60-67, 1989. Type: Article
Sep 1 1989

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2023 ThinkLoud®
Terms of Use
| Privacy Policy