Deriving the Composition of Binary Topological Relations
Max Egenhofer Journal of Visual Languages and Computing 5 (2): 133-149, 1994.
Abstract
A new formalism is presented to derive knowledge about the
composition of two binary topological relations over a common
object. The formalism is based on a topological data model and
compares the nine empty and non-empty intersections of interiors,
boundaries, and exteriors between two objects. Based upon the
transitivity of set inclusion, the intersections of the composed
topological relations are derived. These intersections are then
matched with the intersections of the eight fundamental topological
relations, giving an interpretation to the composition of
topological relations. The result of this study is the composition
table of the eight binary topological relations that exist between
n-dimensional point sets with a codimension of 0. While the
combined topological relations are unique for some compositions,
more than half of all possible compositions are disjunctions of
possible relations. Geometric prototypes are shown for the
2-dimensional case. The composition table enables topological
reasoning at the conceptual level of relations, rather than having
to calculate all relations from the representation of the spatial
objects. Its practical value is that it can serve as in a
computational model for an assessment of whether a set of
topological predicates is consistent or not and in spatial query
processing when no explicit information about spatial relations is
available.
Full article
Max Egenhofer
