Jochen Albrecht and Hans Guesgen

Department of Geography - Department of Computer Science

The University of Auckland, Private Bag 92019, Auckland, New Zealand

Email: j.albrecht@auckland.ac.nz, hans@cs.auckland.ac.nz

The concept of space underlying geographic information systems
is basically Euclidean and most attempts to deal with imprecise
or uncertain geographic information try to accommodate for this
imperfection rather than to change the conceptual view. In this
paper, we describe a way of incorporating imprecise qualitative
spatial reasoning with quantitative reasoning in geographic information
systems (GIS). In particular, we show how the common models of
geometry can be extended to allow for qualitative spatial reasoning.
The idea is to use fuzzy sets to model qualitative spatial relations
among objects, such as *The downtown shopping mall is close
to the harbour*. The membership function of such a fuzzy set,
in this instance, defines a fuzzy distance operator.

We illustrate a way of incorporating imprecise qualitative spatial reasoning with quantitative reasoning in GIS. For this, we develop a data model to support qualitative spatial reasoning based on constraints, and we provide an example to illustrate our model. We propose a set of locations, each consisting of a vector of base values. We then associate fuzzy membership functions with the locations to describe qualitative spatial information, from which spatial relations and queries can be computed, regardless of the crispness/fuzzyness of the base data.

Keywords: qualitative reasoning, distance operator, proximity measure, perceived space

In spite of their name, GISs have so far been mostly be geometric
in nature, ignoring the thematic and temporal dimensions of *geographic*
features (Molenaar 1996, Sinton 1978, Usery 1996). Various attempts
to overcome these limitations have been documented in a number
of disciplines (Frank 1992, Goodchild 1992, Gupta *et al.*
1991, Herring 1991, 1992, Raper and Maguire 1992). Several publications
deal with extensions of the data model while Allen's work on temporal
logic forms the basis for numerous endeavours to deal with dynamic
aspects of geographic information (Egenhofer and Golledge 1997,
Frank 1994, Peuquet 1994). Applications of fuzzy techniques are
most commonly found in remote sensing literature (Altmann 1994,
Brimicombe 1997, Molenaar 1996, Plewe 1997) but the inherent fuzziness
of geographic features becomes increasingly acknowledged in the
geographic information science as well. The notion of qualitative
reasoning stems originally from artificial intelligence and has
been applied to spatial phenomena only since about 1990 (Freksa
1990, Hernández 1991, Mukerjee and Joe 1990) but has become
well established with conference series such as COSIT and the
European research initiative SPACENET. Each of these areas will
be briefly described, providing the context for the application
of qualitative reasoning in the absence of precise geographic
data.

A framework, outlining the concept of a hierarchy of spaces, links the different approaches and forms the epistemological background for a new data model proposed in this article. This data model resembles the field view (Goodchild 1992, Worboys 1995) of current GIS, in that it defines (a) a vector of base values for each areal unit and (b) relations and queries on these base values in the form of equations. These equations, however, are based on fuzzy sets rather than crisp sets, and they can be defined across spatial and non-spatial dimensions of the vectors comprising the base data. This way, the whole bounty of (current) GIS operations (requiring crisp data) can be applied to fuzzy data as well.

There is a quite extensive body of literature on the use of fuzzy logic in 2-dimensional spatial applications. One of the first authors to introduce this concept to the area of GeoComputation even before this term had been invented, was Peter Burrough with his standard textbook (1986). While the techniques have been sophisticated since then, the main ideas have remained unchanged, although the range of applications has spread from map-based modelling to now include spatial decision support (Saint-Joan and Mezzadri-Centeno 1998), hierarchical spatial reasoning (Frank 1998), user interface design (Wang), and even psycho-linguistics (Rodrigo and Guesgen). The focus of these authors is on the spatial and semantic fuzziness of geographic objects (Burrough and Frank 1996). Even where operators on fuzzy sets have been defined (e.g. Burrough and McDonnell 1998, p. 274), they are by definition limited to set-based operations and hence possess a rather low-level functionality. They are adequate for the ubiquitous overlay operation but are not to much avail in concert with most of the other fundamental GIS operations (Albrecht 1998) such as 'nearest neighbour' or 'path analysis'.

**The Combinatorial Approach**

Atkin (1974), and subsequently Gould (1981), Johnson (1981), Beaumont
(1984) and others have introduced the algebraic-topological method
of * Q*-analysis as a mean to describe set relations
and hierarchical structures in social and planning sciences. Originally,

__Union and Intersection__

The two most basic GIS operations *union* and *intersection*
are fundamental in dealing with (fuzzy) sets as well. If {*Si*},
*i Î I*, is any family of
sets indexed by some *I*, then the union of this family of
sets is {*x | x Î Si*, for
at least one *i Î I*}. The
union {*Si*}, *i Î I*,
may be denoted by ,
or I}.
The intersection of this family of sets is {*x|x Î
Si* for every *i Î I*,
that is, *x* is an element of every member of the family
of sets}.

__Distance__

A *metric space* is a set in which we have a measure of the
closeness or proximity of two elements of the set, that is, we
have a *distance* defined on the set. A metric is nothing
more than the ordinary notion of distance. A set *X* with
metric *D* is said to be a metric space, and may be denoted
by *X*, *D*. This distance function may also be expressed
in terms of a mapping from *V ´
V* into the field of scalars Â.
It is then expressed as *d : V ´
V ® Â*
with

(2)

(3)

__Neighbourhood__

Let *X*, *D *be a metric space. If *x* is any point
of *X*, then we may want to consider all the points of *X*
within a certain distance of *x*, that is, the set of points
of *X* which are within some degree of nearness to *x*.
Expressed more formally, if *X*, *D* is a metric space,
*x Î X*, and *p* is
a positive real number, then the *D*-*p*-neighbourhood
of *x* is defined to be the set of all points *y* of
*X* such that *D(x, y) < p*; that is, the *D*-*p*-neighbourhood
of *x* is defined to be {*y Î
X | D(x,y) < p*}. Where there is no danger of ambiguity,
the *D*-*p*-neighbourhood of *x* will be called
the *p*-neighbourhood of *x* and will be denoted *N(x,
p)*. If *X*, *D* is a metric space and *p* is
any positive number, then the *D*-*p*-neighbourhood
*N(x, p)* of any *x Î
X* is an *open set*.

Reasoning about neighbourhoods differentiates between operations on open sets (boundaries are not included) and closed sets (boundaries are included). Consequently, the rules for 4-intersections and 9-intersections (Egenhofer and Herring 1990) can be applied.

This definition of neighbourhood can be applied to any *n*-dimensional
object. A number of well-known, but usually difficult to formalise,
spatial concepts may be derived from this definition. A set theoretical
definition of *nearness*, for example, assumes each point
*x* to be part of a neighbourhood *X*. Nearness then
means that two points have some overlapping neighbourhoods (see
Figure 2).

__Eccentricity__

We can define the eccentricity *e* of a simplex in a form
that conforms closely to our everyday use of the word. We call
the dimensionality of a simplex top-*q* or ,
and the dimensionality at which it begins to connect with other
simplices bottom-*s* or .
Then one measure of eccentricity is

Gatrell (1991, p. 119) defines space as "a relation defined
on a set of objects", which includes just about any structured
collection. While singular sets allow for a very limited set of
operations only, the relations between two or more sets do provide
some powerful methods of (spatial) reasoning. Traditionally, spaces
are represented in some form of geometry (thereby neglecting the
realms of attribute spaces). The new data model, proposed in this
paper, combines *n*-dimensional * Q*-analysis
with a fuzzy set theoretic reasoning. Based on Beguin and Thiesse
(1979) we define a place

The conference presentation will mainly consist of some examples for the new types of queries that can be expressed using the combinatorial fuzzy logic model. Current GIS can be customised to perform an of the queries given beneath, however, the advantage of our proposed model is that it requires no customisation other than a dictionary / library of natural language expressions. The operations in any case are analogue to those implemented in crisp Euclidean-based GIS. Examples for this type of queries are:

- Which two neighbouring places in Central Europe had a high intensity rainfall event last year?
- Name two neighbouring places, at least one of which offers good job opportunities while the other one has superb recreational properties.
- Which combinations of work and residence locations offer good shopping opportunities on an acceptable commuting route?

Altmann, D. 1994. Fuzzy set-theoretic approaches for handling
imprecision in spatial analysis. *International Journal of Geographical
Information Systems*, **8**(2):271-189.

Atkin, R. 1974. An approach to structure in architecture and urban
design. *Environment and Planning B* **1**:56-67,173-191.

Albrecht, J., 1998. Universal Analytical GIS Operations, In Craglia,
M and H. Onsrud (Eds) *Geographic Information Research: transatlantic
perspectives*. London: Taylor & Francis. (in press)

Beaumont, J. 1984. A description of structural change in a central
place system: a speculation using Q-analysis. *International
Journal of Man-Machine Studies* **20**:567-594.

Beguin H. and J. Thiesse, 1979. An axiomatic approach to geographical
space, *Geographical Analysis*, **11**:325-341.

Brimicombe, A. 1997. A universal translator of linguistic hedges
for the handling of uncertainty and fitness-of-use in GIS. In
Z. Kemp (Ed), *Innovations in GIS 4*, pp. 115-126. London:
Taylor & Francis.

Burrough, P. 1986. *Principles of Geographical Information Systems*.
Oxford: Oxford University Press.

Burrough P. and A. Frank (Eds) 1996. *Geographic Objects with
Indeterminate Boundaries*. GISDATA 2. London: Taylor &
Francis.

Burrough, P. and R. McDonnell 1998. *Principles of Geographical
Information Systems*. 2º, Oxford: Oxford University Press.

Couclelis, H. 1996. A typology of geographic entities with ill-defined
boundaries. In Burrough, P. and A. Frank (Eds) *Geographic Objects
With Indeterminate Boundaries*, pp. 44-55, GISDATA 2, London:
Taylor & Francis.

Egenhofer, M. and R. Golledge 1997. *Spatial and Temporal Reasoning
in Geographic Information Systems*. New York: Oxford University
Press.

Egenhofer, M. and J. Herring, 1990. A mathematical framework for
the definition of topological relationships. In Brassel, K. and
Kishimoto, H. (Eds) *Proceedings of the 4th International Symposium
on Spatial Data Handling*, Zürich, pp. 803-813.

Frank, A. 1992. Spatial concepts, geometric data models, and geometric
data structures. *Computers and Geosciences*, **18**:409-417.

Frank, A. 1994. Qualitative temporal reasoning in GIS-ordered time scales. In Proceedings Symposium on Spatial Data Handling. Edinburgh, Scotland. pp. 410-431

Frank, A. 1998. 'Metamodels for Data Quality Description'. In Jeansoulin, R., and M. Goodchild, (Eds) Data quality in Geographic Information: from Error to Uncertainty. Paris: Editions Hermès.

Fisher P. 1998. Sorites paradox and vague geographies. *Transactions
of the Institute of British Geographers* (in press).

Freksa, C. 1990. Qualitative spatial reasoning. Proceedings Workshop RAUM, Koblenz, Germany, pp. 21-36.

Gatrell, A. 1991. Concepts of space and geographical data. In
Maguire, D. *et al.*, (Eds) Geographical Information Systems,
Vol 1, Harlow: Longmans, pp. 119-134.

Goodchild, M. 1992. Geographic data modeling. *Computer and
Geosciences*, **18**:401-408.

Gould, P. 1981. A structural language of relations. In Craig, R and M. Labovitz (Eds) Future Trends in Geomathematics. London: Pion.

Gupta, A., T. Weymouth and R. Jain 1991. An object-oriented data model for large image bases. In Günther O. and H. Schek (Eds), Advances in Spatial Databases, Lecture Notes in Computer Science 525, pp. 45-61. Berlin: Springer.

Hernández, D. 1991. Relative representation of spatial knowledge: the 2-D case. In Mark, D. and A Frank (Eds), Cognitive and Linguistic Aspects of Geographic Space, pp. 373-385. Dordrecht: Kluwer.

Herring, J. 1991. The mathematical modeling of spatial and non-spatial information in geographic information systems. In Mark, D. and A Frank (Eds), Cognitive and Linguistic Aspects of Geographic Space, pp. 313-350. Dordrecht: Kluwer.

Herring, J. 1992. TIGRIS: A data model for an object-oriented
geographic information system. *Computer and Geosciences*,
**18**:443-452.

Johnson, J. 1981. Some structures and notation of Q-analysis.
*Environment and Planning B* **8**:73-86.

Kemppainen, H. and J. Albrecht 1996. Scalability of Spatial Operators.
*Proceedings GIS/LIS'96* 18-21 November 1996 Denver CO, pp.
162-172.

Molenaar, M. 1996. The extensional uncertainty of spatial objects. in Proceedings Symposium of Spatial data Handling 96, pp. 9B1-13. Delft, The Netherlands.

Mukerjee, A. and G. Joe 1990. A qualitative model for space. In Proceedings AAAI-90, pp. 721-727. Boston, MS.

Nystuen, J. 1963. Identification of some fundamental spatial concepts.
*Papers of the Michigan Academy of Sciences* **48**, pp.
373-384. Reprinted in Berry, B. and Marble, D., (Eds) *Spatial
Analysis: a reader in statistical geography*. Englewood-Cliffs:
Prentice-Hall, pp. 35-41.

Peuquet, D. 1994. It's about time: A conceptual framework for
the representation of temporal dynamics in geographic information
systems. *Annals of the Association of American Geographers*,
**84**(3):441-461.

Plewe, B. 1997. A representation-oriented taxonomy of gradation. In Hirtle, S. and A. Frank (Eds), Spatial Information Theory: A Theoretical Basis for GIS, Lecture Notes in Computer Science 1329, pp. 121-136. New York: Springer.

Raper, J. and D. Maguire 1992. Design models and functionality
in GIS. *Computer and Geosciences*, **18**: 387-394.

Rodrigo, S. and H. Guesgen 1998. Fuzzy spatial reasoning in psycholinguistic
experiments on braille reading. *Proceedings IEEE International
Conference on Fuzzy Systems (FUZZ-IEEE '98)*, pp. 216-219,
Anchorage, Alaska.

Saint-Joan, D. and T. Mezzadri-Centeno 1998. GEODES: A Fuzzy Expert
System for Spatial Decision Support with GIS. *Proceedings Information
Processing and Management of Uncertainty in Knowledge-Based Systems*,
6-10 July 1998, Paris, France.

Sinton, E. 1978. The inherent structure of information as a constraint
to analysis: Mapped thematic data as a case study. In Dutton,
D. (Ed) *Harvard Papers on Geographic Information Systems, Vol
6*. Reading: Addison-Wesley.

Usery, L. 1996. A conceptual framework and fuzzy set implementation
for geographic features. In Burrough, P. and A. Frank (Eds), *Geographic
Objects with Indeterminate Boundaries*, GISDATA Series 2, pp.
71-85. London: Taylor & Francis.

Worboys, M. 1995. *GIS-a computing perspective*. London:
Taylor and Francis.