Abstract: Based on Egenhofer’s nineteen relations between line and region, algorithm OR was presented and verified. Via algorithm OR, the topological relation matrix between a composite line and a region can be derived. Five mutually exclusive relations, denoted by SM, were distinguished from the original nineteen relations by means of algorithm OR. It was proved that SM was the minimal set of basic relations to express the nineteen relations. SM is useful for reasoning complex relations between line and region, and makes it more concise to represent the topological relations between line and region. In order to further study the reasoning of the topological relations between line and region, the derivation graph for deriving other relations from SM was given.

Key words: topological relation, line, region, OR algorithm