Spatial relations between indeterminate regions

Systems of relations between regions are an important aspect of formal theo ries of spatial data. Examples of such relations are part-of, partially ove rlapping, and disjoint. One particular family of systems is that based on t he region-connection calculus (RCC). These systems of relations were origin ally formulated for ideal regions, not subject to imperfections such as vag ueness or indeterminacy. This paper presents two new methods for extending the relations based on the RCC from crisp regions to indeterminate regions. As a formal context for these two methods we develop an algebraic approach to spatial indeterminacy using Lukasiewicz algebras. This algebraic approa ch provides a generalisation of the "egg-yolk" model of indeterminate regio ns. The two extension methods which we develop are proved to be equivalent. In particular, it is shown that it is possible to define part-of in terms of connection in the indeterminate case. This generalises a well-known resu lt about crisp RCC regions. Our methods of extension take a relation on cri sp regions taking values in the set of two Boolean truth values, and produc e a relation on indeterminate regions taking one of three truth values. We discuss how our work might be developed to give more detailed relations tak ing values in a six-element lattice. (C) 2001 Elsevier Science Inc. All rig hts reserved.