Mereogeometry and Pictorial Morphology


Autoren: Stefano Borgo, Roberta  Ferrario, Claudio Masolo, Alessandro  Oltramari
[erschienen in: Computational Visualistics and Picture Morphology (Themenheft zu IMAGE 5)]

Schlagwörter: [Schlagwörter]

Disziplinen: logic, cognitive science, computational geometry, formal ontology


The paper reviews geometrical approaches in the area of qualitative space representation by discussing formal systems of geometry based on the notion of extended regions (mereogeometries). The focus is on primitives that are cognitively motivated and that capture different notions of naive geometry. The paper then moves to consider the role of mereogeometries (and in particular of the concepts they rely upon) in the domain of picture morphology in two ways: it discusses some primitives that are motivated from the cognitive perspective, and it considers the issue of granularity and refinement.

1 Introduction

Space, as the realm of physical locations or as the structure where to organize knowledge, has always been at the center of scientific research. In this work we look at space in two distinct senses: on the one hand the characterization of physical space as provided by mereogeometries [6], on the other the study of space in the light of pictorial representation and, more specifically, of pictorial morphology [38]. If mereogeometries are the result of a formal approach to geometry that was primarily developed in the 20th century and that tries to do justices of cognitive and foundational principles, pictorial morphology is the research area where images are analyzed and decomposed with tools inspired by techniques developed in linguistics (e.g. generative grammars). The two approaches are fairly recent and their possibility of interaction seems strong. The paper first reviews the motivations and the development of mereogeometries and then moves to investigate the relationships between mereological primitives and research in pictorial morphology. The goal is not to set a precise comparison, which would be premature since the connection between these areas is still in a primitive state, but to look at commonalities and to suggest possible future investigations in the respect of the particularity and aims of each discipline.

2 Mereogeometry

Mereogeometry is a form of geometry (that is, a mathematical theory) that has found its place not in the usual mathematical community but within the knowledge representation area and, more precisely, in the domain of qualitative representation. The interest on representation of space based on mereology (i.e., the relation of parthood over extended regions) goes back at least to Lobacevskij [28] but it has not catch the attention of a consistent number of researchers before the end of the last century. From the 90s, research on this topic has finally become consistent and the number of papers devoted to this area has regularly increased since then.

Going back to what we may consider the beginning of research in mereogeometry, we find Lobacevskij’s work [28] (published in 1835) where the author posits as task of his research the search of an alternative to the axiomatic foundation of geometry based on points. At the time, geometry was by antonomasia Euclidean geometry. However, some researchers were pointing out that this system falls short of satisfying cognitive concerns being based on the cognitively disputable notion of point. Indeed, human experience of space is experience in magnitude and points cannot be empirically experienced. Nonetheless, what should be taken as ground for a cognitively and philosophically sound geometrical system and what properties such a system should have was not clear yet. Taking solids as basic entities for his system, Lobacevskij revolutionizes the foundations of geometry from the ontological viewpoint and begins a new field to fill the gap between geometrical and spatial entities.

Little by little, systems of mereogeometry (although not yet called in this way) started to be introduced and discussed with particular emphasis on cognitive soundness and expressiveness. As one could expect, at the beginning the aim was to show that the concept of point is not necessary for the foundation of geometry. After all, the standard approach at the time was to define regions as sets of points. This topic pervades the works of Whitehead [49], De Laguna [16], Nicod [31], Tarski [46], and Grzegorczyk [26]. With the introduction of formal techniques to reconstruct points from extended regions, the different conceptualizations of space that were proposed in those years could be seen from a more rigorous perspective. Now the attention was driven to the properties of space, the primitive relations, and the ontological nature of the entities in the adopted domain of discourse. In particular, these authors talk of apparently different entities like solids, extended regions, bodies, and volumes. In some cases these notions are used just informally, and it is diffcult to understand the presuppositions or the basic intuitions about (physical) objects and their possible locations in space. In addition, some authors have developed mixed theories where the domain of discourse includes entities of different dimensions like points, lines, surfaces, and volumes (Gotts [25] and Galton [23]).

While classical geometry had already been defeated as ‘the geometry of physical space’ after the introduction of relativist physics, the centrality of Euclidean geometry was now substantially questioned even at the level where it is most successful: the layout of our everyday space. The revolution was brought by the definition of points as particular sets of regions. Since the new theories succeeded in defining Euclidean entities and relations within a different domain, one cannot rely on purely formal arguments to establish which entities and relations deserve the role of geometrical primitives. Euclidean geometry is challenged to defend itself on the choice of the basic entities, an issue that has always been avoided by pointing at the successful history of the discipline in modeling space intuitions.

But now merogeometries have reached a level of formal clearness and are supported by arguments that arise in the new studies of the relationship between humans, their perceptual and cognitive apparata, and their experienced knowledge of space. Here, region-based geometries seem to be cognitively more appealing since they make possible an (almost) direct mapping from empirical entities and laws to theoretical entities and formulas. At the same time, the new entities are openly discussed: the consequences of choosing extended regions as primitive entities, the meaning of empirically experiencing extended regions, the role of perfect regions in geometrical construction.

It has been with the work of Clarke [8, 9] that theories based on extended entities have shown their potentialities for both their formal aspects and their possible use in application. Furthermore, the ontological clearness and the evident connection with physical entities justify the interest of philosophers. The relations of parthood (Greek meros = part, hence mereology: ) and connection (topology) are here taken to be fundamental notions exemplified by spatial or material entities like physical objects, chunks of matter, holes, etc. (see Simons [42], Casati and Varzi [7], and Smith [43]). Nowadays, these theories are known as mereotopologies. Then, we can look at mereogeometries as theories that extend mereotopologies with predicates and/or relations of geometrical import. They may be motivated from different research domains, as it will be explained below, since the general idea is to reconstruct a commonsense notion of space as it is understood in those domains.

Although space has been traditionally captured by point-based geometry, it must be recognized that, overall, the properties of Euclidean space fit our commonsense notion of space. Thus, it should not be surprising that most mereogeometries lead to systems ‘equivalent’ to Euclidean geometry [6]. This very fact shows how our cognitive perception of space is quite stable and precise and is not a ected by the choice of geometric primitives. Indeed, the properties that commonsense space should satisfy are not an issue. The crucial point is how we cognitively attain this specific notion of space. In this perspective, the first question that mereogeometries try to answer is what primitives apply to extended objects and are expressive enough to generate the commonsense notion of space.

Mereogeometries natuarlly arise in various areas. In Schmidt [39] physics is presented as a theory based on extended entities. This theory allows us to refer explicitly to the objects involved in experiments. Generally speaking, cognitive science and computational linguistics analyze the possibility of formalizing human learning, conceptualization, and categorization of spatial entities and relations. In particular, Renz and al. [37] take into account the cognitive adequacy of topological relations while Aurnague et al. [1] and Muller [29] show how mereogeometrical notions are central in the semantics of natural language. Donnelly [17] formalizes the theory of De Laguna in the perspective of common-sense analysis of spatial concepts. In computer science and more specifically in qualitative spatial representation and reasoning (see Cohn and Hazarika [14] and Vieu [48] for good overviews), mereogeometries are applied for modeling qualitative morphology and movement of physical bodies (Bennett et al. [2, 3, 4], Borgo et al. [5], Cristani et al. [15], Dugat et al. [19], Muller [30], Galton [22], Li et al. [27], Randell et al. [34, 35]), for describing geographical spaces and entities in Geographical Information Systems (Pratt-Hartmann and Lemon [32], Pratt-Hartmann and Schoop [33], Stock [45]), as well as for characterizing medical and biological information (Schulz [40], Cohn [12], Smith and Varzi [44], Donnelly [18]).

In all these areas, specific foundational and applicative concerns affect the development of the theories based on geometrically extended entities. Indeed, in the literature there are numerous mereogeometries which differ on primitive entities, formal properties, as well as general principles. Unfortunately, due to technical diffculties, there are just a few formal studies on the relationships among mereogeometrical systems. In particular the poor axiomatization of most mereogeometries and the lack of a general methodology further complicate the task. A more systematic comparison is encouraged to facilitate both reuse and communication among applications based on different systems.

Basic Terminology

The study of space is made possible by adopting a few well defined concepts. Although in this paper we do not need to look at the precise formal definitions (we will present them in simplified terms), it is always good to try to understand the details and the ontological meaning of a defined concept. The interested reader can look at [42] for a more in depth analysis of mereotopological terms and [6] for the mereogeometrical terms.

At the basis of topology we have the notion of open set. An open set is a set that does not contain its boundary: examples are (0, 5) in the one dimensional space ℜ1 (the real line) and {(x, y) | x2 + y2 < 1} in the two dimensional space ℜ2. The dual notion is that of closed set, that is, a set that contains its boundary like [0, 5] in ℜ1 and {(x, y) | x2 + y2 ≤ 1} in ℜ2. For a physical example, think of an apple with an extremely thin (we would say ‘infinitely thin’) skin: the apple without the skin fills an open set, with the skin a closed set. In general, given an open set A, the corresponding closed set is the smallest closed set B that contains A (in turn, A is the biggest open set contained in B). The closure operator highlights this relationship: given an open set A as before, the closure of A is the set B. The difference between an open set and its corresponding closed set is called the boundary. Then, for any set C, C plus its own boundary is closed (indicated by [C]) while what remains of C after its boundary has been dropped is an open set (indicated by C°). Note that the empty set and the universe of domain have no boundary and thus are at the same time open and closed.

A regular set A is a set stable under the operations of topological closure (i.e. [ ] and its dual °) in the sense that: 1) the closure of a regular set A is equal to the closure of the corresponding open set (formally [A] = []) and 2) the open set of a regular set A is equal to the open set of its closure [A] (formally = [A]°). These regions are dimensionally homogeneous in the sense that the conditions exclude objects of mixed dimensions. For example, in ℜ3 a solid cube with a point removed or a solid cube with an external segment attached to it are not regular. Finally, since a regular set may be neither open nor closed, an open regular set is a regular set which is also open. Analogously for closed regular sets.

Informally, two sets are said to be connected when ‘they touch each other’. There are several ways to make precise this notion. Below we use it in the following sense: given two non-empty sets A and B, they are connected if [A] and [B] (i.e., their closures) share at least one point.

The notion of self-connection is introduced to talk about sets that are not scattered, they are ‘single pieces’ so to speak. A set A is self-connected if it is impossible to split A in two non-empty sets without generating a new extended boundary in each of the parts. The intuition behind this notion is easily grasped when we look at physical objects. Take a chocolate bar: if we image to cut the bar in two parts, we know that each part will present some ‘extended’ new boundary, namely where the cut takes place (‘extended’ because it is not just a point or a line; it is a new piece of surface). Compare this with a set of candies: we can split the candies in two groups (dividing them by color or brand or flavor) without generating any new boundary.

The notion of congruence captures the idea of objects of same shape and same size. If two objects are congruent, each can fill up the same location that the other does. Relatively to abstract geometrical entities, this notions can be rephrased as: two sets of points are congruent if it is possible to move one over the other (or over a symmetric image of the other) so that each point of the first is colocated with a point of the second and vice versa. Note that the movement must be ‘rigid’, that is, in the movement to fit the other set, no part of the geometrical entity must undergo squeezing or stretching.

3 Mereogeometries, Primitives and Interpretations

The formal interpretation of the non-logical primitives is crucial to understand the expressiveness and the cognitive plausibility of a logical system. For instance, researchers have been interpreting the notion of ‘extended region’ using different sets of geometrical loci. Common to most approaches is the interpretation of extended regions as regular sets in the space ℜn (where n is the dimension of the space one is modeling). However, rarely all regular sets are considered; often one restricts the interpretation to the subclass of open regular sets, closed regular sets, polygonal regular sets, finite regular sets, and so on.

Unfortunately, especially in the early works in mereology, this aspect has been mostly neglected. However, to be honest, even in recent literature it may happen that the formal interpretation of the primitives is not addressed. Indeed, sometimes researchers relay on intuitive interpretations and focus just on formal and implementation properties of the primitives. In these cases, the satisfaction of interesting properties is considered as the preliminary condition that may motivate a subsequent logical formalization. In other approaches, the goal of the research is limited to the construction of computationally effcient systems, and, in these cases, the logical formalization is not even attempted.

If one wants to consistently analyze and make a comparative study of these mereogeometrical systems, one needs to start with a general discussion on implicit assumptions which motivate the intended interpretation of the non-logical vocabulary and the adopted domain of discourse. Without this analysis, we suspect, it is unrealistic to look for a suitable (or even correct) framework for a comparison. An example in this sense is carried out in [6]. This work discusses and compares some systems of mereogeometry based on different primitives and different domains that we report here.

T1:

We begin with the mereogeometry presented in [46] and further developed in [2, 4]. Here there are two primitives: the binary relation P of parthood (P(x, y) stands for “region x is part of region y”) and the predicate S of sphere (S(x) stands for “region x is a sphere”). The theory has been developed for the domain of non-empty regular open subsets of ℜn. The idea is that P can be interpreted as set-inclusion among regions of points in ℜn and that S corresponds to the notion of ball in ℜn.(1)



Figure 1: x is part of y, P(x, y); z is a sphere, S(z).


T2:

This theory was presented in [6] and adopts three primitives: P, SR, CG. The first is the relation of parthood we have seen in T1. SR is the predicate of self-connectedness: SR(x) is read “region x is self-connected” (see Fig. 2). Finally, GC is the binary relation of congruence: CG(x, y) stand for “regions x, y are congruent”. The domain for the theory is given by the non-empty regular open subsets of ℜn with finite diameter. That is, compared to T1, the theory discharges infinite regions.



Figure 2: x and y are connected, C(x, y); w is self-connected, SR(w), while z and v are not; z and v are congruent, CG(z, v).


T3:

The third system was given in [31] and is based on the primitives P and Conj. As before, P is the relation of parthood. Conj is the quaternary relation of conjugateness: Conj(x, y, z,w) stands for “regions x, y and z, w are conjugate”. Informally, this means that there is a point(2) px in x, a point py in y, a point pz in z and a point pw in w such that the distance between px and py equals the distance between pz and pw (see Fig. 3). The domain of this theory is the set of non-empty regular closed subsets of n which are self-connected. Compared to T1, the theory discharges scattered regions.



Figure 3: x, y and z, w are conjugate, Conj(x, y, z,w).


T4:

Next, we have the mereogeometry introduced in [16] and further developed in [17]. This time we have just the primitive dubbed can-connect and indicated by CCon. CCon(x, y, z) stands for “region x can connect both regions y and z”. The idea is that the length of the diameter of region x is at least as the distance between regions y and z: intuitively, if this holds, one can ‘move’ x in a position where it is in contact with both y and z (see Fig. 4). The domain is more restricted than those seen so fare: it takes only non-empty regular closed subsets of n which are both self-connected and finite. Compared to T1, the theory considers closed regions only and discharges both scattered regions and infinite regions.



Figure 4: x can connect y and z, CCon(x, y, z).


T5:

The system introduced in [47] was later further developed in [1]. In this mereology, the primitives are the binary relation C of connection and the ternary relation Closer of closerness. C(x, y) stands for “region x is connected to region y” and Closer(x, y, z) for “region x is closer to region y than to region z” (see Fig. 5). The domain for this theory is the set of non-empty regular subsets of n. That is, it is larger that the domain of T1 since the latter takes the open regular regions only.



Figure 5: x is closer to y than to z, Closer(x, y, z).


T6:

Finally, we consider the system given in [11, 10, 13]. Here there are two primitives: the binary relation C of connection already seen in T5 and the binary relation ConvH of convex-hull: ConvH(x, y) stands for “region x is the convex hull of region y” (see Fig. 6). The theory takes as domain the set of non-empty regular open subsets of n like in T1.



Figure 6: x (corresponding to region y plus the areas enclosed by the dash lines) is the convex-hull of y, ConvH(x, y).


Although these theories adopt quite disparate primitives, in [6] it has been shown that they are closely tied. To appreciate their interrelationships, we need first to introduce some notions.

Informally, the comparison between two systems consists in showing that everything that can be said in one system can be said in the other, and furthermore, that everything which holds in one system holds in the other as well. In logic, this result is usually obtained via the notion of ‘explicit definition’ that amounts to showing that what is primitive in one system can be defined in the other. However, here the comparison is complicated by the lack of axiomatization of some theories, a diffculty increased by the fact that the theories rely on different domains of discourse. For this reason, we generalize the notion of explicit definition as follows.

Definition 3.1 If A is a primitive of a theory T, we say that A is explicitly definable in another theory T' for a domain D if there exists an expression Φ in the language of T' such that the interpretations of P and Φ are equivalent for their structures with domain D.

If we forget the reference to domains, the notion of explicit definition leads to the classical notion of equivalence among theories. Two theories are equivalent if all the primitives of the first are explicitly definable in the second, making the first a subtheory of the latter, and vice versa. However, for mereogeometries the dependence on the domain is crucial. Then, we need to introduce the generalized notions of subtheory and equivalence.

Definition 3.2 A theory T is a subtheory of T' for domain D if every primitive T has an

explicit definition in T' for that domain.

Now, it becomes possible to capture a notion of equivalence, called conceptual equivalence, that is suited to mereogeometries. Basically, it relativizes equivalence to logical structures.

Definition 3.3 Let T and T' be theories with domains Di and Dj , respectively, T and T' are conceptually equivalent if T is a subtheory of T' and T' is a subtheory of T with respect to both Di and Dj.

The results in [6] can now be formulated as follows.

Theorem 3.1

- Theories T1, T2, T3, T4, T5 are equivalent;

- T6 is a subtheory of all theories T1, T2, T3, T4, T5;

- T1, T2, T3, T4 are conceptually equivalent.

Theories T1, T2, T3, T4 have the characteristics of a complete geometry and are called full mereogeometries. The other two systems are set apart for different reasons. T5 is as strong as the previous but it is associated to a much richer domain where regions of different dimensions can coexist. The analysis of this domain seems to require further considerations. Theory T6 is representative of a large number of mereogeometries. This and many other systems in the literature, e.g. the Lines Of Sight [21] and ROC [36], have limited expressiveness, and their position in the landscape of mereology is not yet clear. Nonetheless, subsystems of full mereogeometries are of great interest since they capture a particular perspective on space whose motivations come from very active areas of research like robotics and qualitative aspects of human perception.

4 Topics across Mereogeometry and Pictorial Morphology

We have seen that mereogeometry stems from the need to study space independently from entities and notions that are out of reach for human perception. This research has two major motivations, which we have not set apart yet, namely the study of space from a cognitive perspective, and the representation of space in qualitative fashion.

In the cognitive perspective, which has implicitly driven the exposition of section 2, the goal is to find a formal characterization of space, as experienced by humans, which rely upon entities and relations that are as much as possible under human perception and (direct) cognitive grasp. The fact that there are several alternative options (as seen in section 3) does not weaken the goal since this area did not su ered from the myth of the ‘true model of space’, a myth that affected the whole history of Euclidean geometry. The other approach is dubbed qualitative. Qualitative systems are formalisms widely studied in the artificial intelligence community since they embrace a perspective strongly focused on the balance between expressiveness and (e ective) computability. In this case, one looks at formal representations of space where, roughly speaking, one can represent a limited set of geometrical properties (like those relevant to perception, navigation or conceptualization of external reality), without the formal complexity intrinsic to point-based geometry. In a nut, the goal is to find ways to represent limited amounts of spatial information avoiding computationally expensive languages.

Both these views have import in the area of pictorial morphology as is pointed out in [38]. On the one hand, the search for grounding pixemes (either as primitives or as prototypical) naturally leads to a discussion which matches the debate on basic geometrical entities. On the other hand, the need of rendering and understanding complex images in a computational setting suggests (at least in theory) the existence of a limited number of basic pixemes that can be combined via a formal calculus of limited complexity, and thus, hopefully, being qualitative. Of course, there is much more in pictorial morphology than this as it was clear from the beginning, see for instance the seminal work of Goodman [24]. While mereogeometry stops at the geometrical aspects of physical objects and their relationships, pictorial morphology has to take into account other elements like granularity (which may affect very basic properties as connectedness among entities, i.e., the topology itself) and appearance (from which the difference between resemblance in geometry and in perception). Indeed, mereogeometry inherits from standard geometry the primary interest in loci and shape description inlcuding features like, e.g., linear borders (the betweenness relationship has been studied both in pointbased and in region-based geometry). The goal, from this perspective, is a formalization of the necessary and suffcient conditions for classifying relevant entities and entity dispositions. Pictorial morphology comes from a broader view where the issue of entity description is subordinated to the primary goal of entity recognition. The interaction between an image and what it depicts is highly intertwined with non-geometrical aspects like experience, expectations, and commonsense reasoning; aspects that go beyond even visual perception. In this context, one cannot disregard forces like gravity (which is intrinsic in the representation/perception of supported and supporting objects), properties like orientation (which is archetypal in animals and buildings), emerging features like density (related to the distribution of objects) and other perceptually relevant characteristics like colors.

Limiting our discussion on the common elements in mereogeometry and pictorial morphology, we should ask what can be learned from the latest results in the study of space. Perhaps, the first observation to make is that mereogeometry corroborates a conclusion that has puzzled researchers in pictorial morphology: the lack of constraints on the choice of primitives. In these domains one arrives easily to equivalent formalisms starting from quite disparate assumptions. It follows that the choice of primitives cannot rely on purely formal properties, it must be supported by arguments and observations from other perspectives like those embedded into the cognitive, evolutionary, mental, and perceptive views. In geometry and mereogeometry we have observed the development of several geometrical systems which, exploiting disparate primitives, naturally lead to formal geometries of equivalent expressiveness.(3) These primitives may capture comprehensive shape descriptions like ‘being a sphere’ [46], may concentrate on local features like ‘having cavities’ [11], ‘having a corner’ [20] (‘forming a right angle’ in Euclidean geometry [41]), or on global properties like ‘being fully symmetrical’ and its opposite,‘ being totally asymmetrical’. The expression ‘fully symmetrical’ is here used to indicate a region which is symmetrical with respect to a given point as well as with respect to all the lines (planes and hyper-spaces in general) through that point. Needless to say that the notion of ‘fully symmetrical region’ brings quickly to the definition of sphere (in any dimension). The expression ‘totally asymmetrical’ instead is satisfied by a region which is asymmetrical with respect to any point, line, plane and hyper-space in general.

All these approaches have been analyzed in two directions: formal expressiveness, and cognitive role. The first issue has brought a series of scattered results which are slowly building up the landscape of the mereogeometries. Cognitively, the result are less promising: no cognitive system seems to be identified as central or primary. One can concentrate on direction or orientation, on distance or size or shape, take into account vagueness, disposition, forms of resemblance etc. The result will be a system, perhaps unusual, perhaps hard to compare to well known geometries and yet it will have that flavor of cognitive adequacy or conformity that will prevent us from discharging it.

5 Mereogeometry as a Tool for Pictorial Morphology

We conclude this excursus on mereology and its relationship to pictorial morphology with a few observations that suggest how results in the first area can help casting light into the second. Although the discussion can apply to the variety of perspectives embedded in pictorial morphology, let us focus on a concept like feature, and on the distinction between content-bearing features and noncontent-bearing features. It is clear that the analysis of resemblance and systems of pictorial representation must make clear what types of features there are and what information they carry. Also, from the arguments presented in this paper, we should not expect mereogeometry to anser the main questions. Still, we know that we can positively look at mereogeometry for important hints. For instance, the settling of the structure and properties of projective mereogeometry (a subdomain that is still not well understood) will help us in isolating the spatial features of prospective representations and how these group together by forming interconnected systems. Such a work is needed to clear up the types of resemblance that properly depend on these features and the interrelations within these types. Similarly, mereology will not tell us what images are or what their content is. Nonetheless, it can be an important tool to determine why pictorial representations follow some spatial rules but not others, and why some relations are necessarily intrinsic (think of the relationship among a picture and its parts, their relative sizes and topological properties) while others may not be.


References

[1] M. Aurnague, L. Vieu, and A. Borillo. La représentation formelle des concepts spatiaux dans la langue. In M. Denis, editor, Langage et Cognition Spatiale, pages 69–102. Paris, 1997.

[2] B. Bennett. A categorical axiomatisation of region-based geometry. Fundamenta Informaticae, 46:145–158, 2001.

[3] B. Bennett, A. G. Cohn, P. Torrini, and S. M. Hazarika. Describing rigid body motions in a qualitative theory of spatial regions. In H. A. Kautz and B. Porter, editors, National Conference on Artificial Intelligence (AAAI’00), pages 503–509. AAAI Press / MIT Press, 2000.

[4] B. Bennett, A. G. Cohn, P. Torrini, and S. M. Hazarika. A foundation for region-based qualitative geometry. In W. Horn, editor, European Conference on Artificial Intelligence (ECAI’00), pages 204–208. IOS press, 2000.

[5] S. Borgo, N. Guarino, and C. Masolo. A pointless theory of space based on strong connection and congruence. In L. Carlucci Aiello, J. Doyle, and S. C. Shapiro, editors, International Conference on Principles of Knowledge Representation and Reasoning (KR’96), pages 220–229. Morgan Kaufmann, 1996.

[6] S. Borgo and C. Masolo. Full mereogeometries. Journal of Philosophical Logic (to appear).

[7] R. Casati and A. Varzi. Parts and Places. The Structure of Spatial Representation. MIT Press, Cambridge, MA, 1999.

[8] B. L. Clarke. A calculus of individuals based on connection. Notre Dame Journal of Formal Logic, 22:204–218, 1981.

[9] B. L. Clarke. Individuals and points. Notre Dame Journal of Formal Logic, 26:61–75, 1985.

[10] A. Cohn, B. Bennett, J. Gooday, and N. Gotts. Representing and reasoning with qualitative spatial relations. In O. Stock, editor, Spatial and Temporal Reasoning, pages 97–134. Kluwer, Dordrecht, 1997.

[11] A. G. Cohn. Qualitative shape representation using connection and convex hulls. In P. Amsili, M. Borillo, and L. Vieu, editors, Time, Space and Movement: Meaning and Knowledge in the Sensible World, Part C, pages 3–16. IRIT, 1995.

[12] A. G. Cohn. Formalising bio-spatial knowledge. In W. C. and B. Smith, editors, International Conference on Formal Ontology in Information Systems (FOIS’01), pages 198–209. ACM Press, 2001.

[13] A. G. Cohn, B. Bennett, J. M. Gooday, and N. Gotts. Rcc: a calculus for region based qualitative spatial reasoning. GeoInformatica, 1:275–316, 1997.

[14] A. G. Cohn and S. M. Hazarika. Qualitative spatial representation and reasoning: An overview. Fundamenta Informaticae, 46(1-29), 2001.

[15] M. Cristani, A. G. Cohn, and B. Bennet. Spatial locations via morpho-mereology. In A. G. Cohn, F. Giunchiglia, and B. Selman, editors, International Conference on Principles of Knowledge Representation and Reasoning (KR’00), pages 15–25. Morgan Kaufmann, 2000.

[16] T. De Laguna. Point, line, and surface. a sets of solids. The Journal of Philosophy, 19:449–461, 1922.

[17] M. Donnelly. An axiomatic theory of common-sense geometry. PhD Thesis, 2001.

[18] M. Donnelly. On parts and holes: The spatial structure of the human body. In M. Fieschi, E. Coiera, and Y.-C. J. Li, editors, MedInfo 04. IOS Press, 2004.

[19] V. Dugat, P. Gambarotto, and Y. Larvor. Qualitative theory of shape and orientation. In R. V. Rodriguez, editor, Workshop on Hot Topics in Spatial and Temporal Reasoning (IJCAI’99), pages 45–53, 1999.

[20] C. Eschenbach, C. Habel, L. Kulik, and A. Leßmöllmann. Shape nouns and shape concepts: A geometry for ‘corner’. In C. Freksa, C. Habel, and K. Wender, editors, Spatial Cognition, pages 177—201. Springer, 1998.

[21] A. Galton. Lines of sight. In AISB Workshop on Spatial and Spatio-Temporal Reasoning, 1994.

[22] A. Galton. Qualitative Spatial Change. Oxford University Press, New York, 2000.

[23] A. Galton. Multidimensional mereotopology. In D. D., W. C., and W. M.A., editors, International Conference on the Principles of Knowledge Representation and Reasoning (KR’04), pages 45–54. AAAI Press, 2004.

[24] N. Goodman. Languages of Art: An Approach to a Theory of Symbols. Hackett, Indianapolis, 1968.

[25] N. Gotts. Formalizing commonsense topology: The inch calculus. In H. Kautz and B. Selman, editors, International Symposium on Artificial Intelligence and Mathematics (AI/MATH’96), pages 72–75, 1996.

[26] A. Grzegorczyk. Axiomatizability of geometry without points. Synthese, 12:228–235, 1960.

[27] S. Li and M. Ying. Region connection calculus: Its models and composition table. Artificial Intelligence, 145:121–146, 2003.

[28] N. I. Lobachevskij. New principles of geometry with complete theory of parallels, volume 2. Polnoe sobranie socinenij, 1835.

[29] P. Muller. ´Eléments d’une théorie du mouvement pour la modélisation du raisonnement spatiotemporel de sens commun. PhD thesis, 1998.

[30] P. Muller. A qualitative theory of motion based on spatio-temporal primitives. In A. G. Cohn, L. Schubert, and S. C. Shapiro, editors, International Conference on Principles of Knowledge Representation and Reasoning (KR’98), pages 131–141. Morgan Kaufmann, 1998.

[31] J. Nicod. La Géométrie dans le monde sensible. Presse Universitaire de France, Paris, 1924.

[32] I. Pratt-Hartmann and O. Lemon. Ontologies for plane, polygonal mereotopology. Notre Dame Journal of Formal Logic, 38:225–245, 1997.

[33] I. Pratt-Hartmann and D. Schoop. Expressivity in polygonal, plane mereotopology. Journal of Symbolic Logic, 65:822–838, 2000.

[34] D. A. Randell and A. G. Cohn. Modelling topological and metrical properties in physical processes. In R. J. Brachman, H. J. Levesque, and R. Reiter, editors, International Conference on Principles of Knowledge Representation and Reasoning (KR’89), pages 357–368. Morgan Kaufmann, 1989.

[35] D. A. Randell and A. G. Cohn. A spatial logic based on regions and connections. In B. Nebel, C. Rich, and W. Swartout, editors, International Conference on Principles of Knowledge representation and Reasoning (KR’92), pages 165–176. Morgan Kaufmann, 1992.

[36] D. A. Randell and M. Witkowski. Using occlusion calculi to interpret digital images. In ECAI’06, pages 432–436, 2006.

[37] J. Renz, R. Rauh, and M. Knauff. Towards cognitive adequacy of topological spatial relations. In C. Freksa, W. Brauer, C. Habel, and K. Wender, editors, Spatial Cognition II, pages 184–197. Springer, 2000.

[38] J.-R.-J. Schirra. Foundation of Computational Visualistics. Deutscher Universitäts-Verlag, Wiesbaden, 2005.

[39] H. Schmidt. Axiomatic Characterization of Physical Geometry. Springer-Verlag, Berlin-Heidelberg, 1979.

[40] S. Schulz and U. Hahn. Mereotopological reasoning about parts and (w)holes in bioontologies. In W. C. and B. Smith, editors, International Conference on Formal Ontology in Information Systems (FOIS’01), pages 210–221. ACM Press, 2001.

[41] D. Scott. A symmetric primitive of euclidean geometry. Indagationes Mathematicae, 18:456-461, 1956.

[42] P. Simons. Parts: a Study in Ontology. Clarendon Press, Oxford, Oxford, 1987.

[43] B. Smith. Basic concepts of formal ontology. In N. Guarino, editor, Proceedings of the First International Conference FOIS 1998, pages 19–28. IOS Press, 1998.

[44] B. Smith and A. Varzi. The niche. Nous, 33:214–238, 1999.

[45] O. Stock, editor. Spatial and Temporal Reasoning. Kluwer Academic Publishers, Dordrecht, 1997.

[46] A. Tarski. Foundations of the geometry of solids. In J. Corcoran, editor, Logic, Semantics, Metamathematics, pages 24–30. Oxford University Press, Oxford, 1956.

[47] J. Van Benthem. The Logic of Time. Kluwer, Dordrecht, 1983.

[48] L. Vieu. Spatial representation and reasoning in artificial intelligence. In O. Stock, editor, Spatial and Temporal Reasoning, pages 5–41. Kluwer, Dordrecht, 1997.

[49] A. N. Whitehead. Process and Reality. An Essay in Cosmology. Macmillan, 1929.



.
Fussnoten:

(1)

(1) Formally, S(x) is translated as: there exists a point c ∈ ℜn and a value r ∈ ℜ+ (the positive reals) such that x = ball(c, r)) (see Fig. 1).

(2)

(2) Recall that x is an extended region and should not be confused with a set of points. However, the formal interpretation takes x to be a set of points and so the informal reading is justified.

(3)

(3) In the light of section 3, equivalence is to be intended "modulo" the choice of the domain.