Undecidability of Plane Polygonal Mereotopology.
Christoph Dornheim · 1998
This paper presents a mereotopological model of polygonal regions of the Euclidean plane and an undecidability proof of its firstorder theory. Restricted to the primitive operations the model is a Boolean algebra. Its single primitive predicate defines simple polygons as the topologically simplest polygonal regions. It turns out that both the relations usually provided by mereotopologies and more subtle topological relations are elementarily definable in the model. Using these relations, Post's correspondence problem, known as undecidable, can be reduced to the decision problem of the model. 1 Introduction Formalizing commonsense concepts of space has received much attention both in the philosophical literature and in recent AI research. Mereotopological theories as well as most calculi for spatial reasoning deal with spatial regions, i.e. the parts of space occupied by physical bodies, and their topological relations as intuitive concepts of our commonsense space. Whereas mereotopolo...