Adrijana Car

Department of Geomatics

University of Newcastle

Newcastle upon Tyne

Email: Adrijana.Car@ncl.ac.uk

Keywords: Hierarchical Spatial Reasoning, Spatial Information Theory, GIS

The main objective of the GeoComputation
conference is to "…provide a forum for the discussion
of emergent computer-based tools and techniques, and their
application to spatial computation" (GeoComputation’98,
Main Objectives, http://www.ggy.bris.ac.uk/geocomp). But, should
every neural network application or cellular automata simulation
be considered for GeoComputation? Catherine Dibble (personal
communication) suggests to adopt *computational Geographic
Science* as "…a much-needed conceptual framework for
distinguishing advances in GeoComputation-methodologies from yet
another application in computationally intensive
techniques." In this paper we argue that Hierarchical
Spatial Reasoning can be used as a GeoComputation-methodology to
design conceptual spatial models using hierarchy as
organizational principle. Moreover, we offer a method and tool to
derive a formal model, and in turn, the computational one to
study the problem(s) of interest.

Hierarchy is one of the most common forms of organizing and structuring complex systems. Spatial Information Science deals with spatial systems which are complex in nature. Research in Spatial Information Theory focuses on conceptualization of space, particularly on conceptual hierarchization of space and spatial phenomena. We understand spatial concepts as spatial objects and spatial relations arranged according to our experience and cognition (Couclelis and Gale 1986). Two issues related to the research on hierarchies and their use for spatial inference can be identified (Stephen Hirtle, personal communication):

*empirical issues*which Golledge (1992, p.2) expressed as the need to "...examine the concept of spatial hierarchy, to identify how such hierarchies are formed and used by people to store and recall spatial organization...", and*computational issues*which consider the use of hierarchy to design and develop computational models, as for example Kuipers’ semantic hierarchy of robot’s movement (Kuipers and Levitt 1988; Kuipers and Byun 1991) or the use of fractals to model cities (Batty and Longley 1994)

The major part of the author’s research
refers to the empirical issues. This paper offers a framework for
research on hierarchies of space based on the general hierarchy
theory (section 2), and how to use the gained knowledge to
improve current spatial reasoning models in GIS or to design more
appropriate ones. In particular, it examines the concepts of
spatial hierarchies attempting to define their common structure
and behavior (i.e., their ontology), and to identify methods for
forming such hierarchies. The major outcome of this research is a
common underlying theory of hierarchical spatial reasoning
(section 3) together with a set of requirements on how to do such
a reasoning. The term *theory* is used here in the natural
scientist’s sense explaining observed regularities that are
empirically testable.

One of the outcomes of this research, however,
refers to the computational issues, i.e., to *implement* a
conceptual model of hierarchical reasoning in a GIS.
Formalization of conceptual spatial models bridges the gap
between conceptual models and their successful implementation for
the following reasons: (1) it helps to understand the underlying
theory and structure, i.e., to describe the meaning of the data
and the model (Dibble 1996), and (2) it provides a basis for
comparison of similar models (Mark and Frank 1989; Egenhofer and
Mark 1995; Mark and Frank 1996). An example illustrates an
application of the hierarchical spatial reasoning to model
wayfinding. It shows how a particular type of hierarchy is used
for spatial reasoning (section 4). We discuss the formalization
method and tool briefly, as sufficient background information is
available in the cited literature (e.g. for formal specification
written in a functional language Gofer is extensively described
in a series of papers compiled by Frank et al. (1997)). In
section 5 we give conclusions and suggest directions for future
work.

Hierarchy is one of the most common forms of organizing and structuring complex systems where a system is subdivided in smaller subsystems, and further subdivision of subsystems can be recursively repeated as long as the subdivision makes sense (Koestler 1967). Such a hierarchical structure can be represented as a tree whose leaves represent the system components. A hierarchy consists of levels each representing a subset of objects selected from the initial set according to some criteria. The number of levels determines the depth of the hierarchy. The number of objects on each level determines its span, and in turn, the span of the hierarchy tree.

Each of these components has local and global
properties. *Local properties* are properties of a level *per
se*, determining objects which belong to a particular
hierarchical level. A local property depends on a context in
which a hierarchy is introduced (e.g., population size is useful
as a criterion for introducing hierarchy of cities, countries or
regional centers, but it is less useful when dealing with road
classification). *Global properties* are independent of the
system’s nature. They describe general structure of a
hierarchy such as:

- A
*part-whole*relationship between the levels - an object on a particular level is a*part*of an object on a higher level, but is a*whole*for objects of the next lower level (Palmer 1977); *Janus-effect*where an object at a particular hierarchical level shows a different face toward the higher level object from the face toward the lower level objects (Koestler 1967); and*near decomposability*which means nesting of systems within larger subsystems (Simon 1973).

Koestler further suggests a rough
classification of hierarchies into *structural and functional
hierarchies*. The first emphasizes the spatial aspect of a
system (a structure of the spatial domain) whereas the second
focuses more on a process as another aspect. These classes tend
to overlap even though the aspects are complementary aspects of
an indivisible spatio-temporal process. Therefore, it is often
useful and necessary to focus on just one of these aspects in
order to successfully solve a task at hand.

Hierarchical Spatial Reasoning (HRS) is a
method of spatial problem solving that uses hierarchy to infer
spatial information and draw conclusions (Car 1997). Hierarchy,
as an abstraction mechanism, is used to decrease the cognitive
load in two major ways: to reduce the complexity of the problem
domain by cutting down the problem space, or it can be used as a *divide
and conquer* method where a problem is divided in smaller
parts and then solved. Both strategies result in an efficient
problem solving because only the necessary data is processed,
usually in a shorter period of time.

One of the outcomes of this research is the requirements for hierarchical spatial reasoning, which state how to perform such a reasoning. The following must be given (Car and Frank 1994):

- A
*hierarchical structure*, that is,

a method to transform a nonhierarchical structure into the equivalent hierarchical one; - A
*set of rules*on how to reason on such a structure, that is,

when and how to switch between the levels;

how to combine partial results obtained at each level into a final result;

transition of objects between the levels, etc.. - A
*comparison of the results*(hierarchical vs. nonhierarchical solution); - An
*analysis of the performance*of the hierarchical algorithm.

The method of hierarchization may provide
non-optimal and/or incorrect results, or even generate these
slower. For example, Shapiro, Weixman and Nir (1992) proposed a
graph with an imposed hierarchical structure, and an adequate,
simple heuristic shortest path search. The calculated paths were
40-50% longer than the optimal paths, thus suboptimal solutions
have been produced. Therefore, the last two requirements have
been added to the set, and can be understood as *quality
control* of hierarchical reasoning.

A number of cognitive studies have shown the
evidence that people may reason hierarchically in geographic
space (Hirtle and Jonides 1985; McNamara, J. K. Hardy and Hirtle
1989). People often use *approximate reasoning* either to
compensate for missing information or to simplify reasoning by
using only information that is needed (Fotheringam 1992). To
account for such reasoning, hierarchical algorithms, which
approximate the strict results, are also of interest. Thus, we
can say that hierarchical spatial reasoning follows patterns of
human cognition, as it computes approximations. The rising
question then is *What is a good enough solution?* rather
than *What is the optimal or strict result?* This is similar
to the economics term *satisficing* which is used when
something is "good enough". The idea in economics is
that people might look around for alternatives until they are
(merely) satisfied, which is not quite the same as looking harder
for the "optimal" alternative (Simon 1979). Thus, we
can talk about *satisficing* versus *optimizing*
solutions. An example addressing this issue is found in (Timpf
and Frank 1997) showing that HSR can compute increasingly better
results and stops the computation when the good enough result is
achieved.

**Classification**. Considering
the classification of hierarchies suggested by Koestler, we
distinguish 2 types of spatial hierarchies (Table 1): functional
spatial hierarchies are based on a task-subtask division and are
useful for modeling spatial processes (e.g., Kuipers’
semantic hierarchy of robot’s movement or landscape modeling
(Lavers and Haines-Young 1993)); structural spatial hierarchies
consider subdivision of a spatial domain resulting in hierarchies
of points, lines and areas.

Functional
hierarchies (process: task - subtask) |
Structural
hierarchies (subdivision of spatial domain) |

a subtask ˜ one level of hierarchy | a subset of data ˜ one level of hierarchy |

different levels => different ontologies | different
levels => the same ontology but different amount of detail |

Table 1: Classification of Spatial Hierarchies

**Hierarchization methods.** At
least two different methods to derive a spatial hierarchy emerged
from analysis of hierarchies for spatial reasoning:

*Bottom-up***:**from a set of objects on one level only a subset is selected for the next higher level, e.g., graph - subgraph;*Top-down*: a n-dimensional spatial object on one level is divided in multiple spatial objects of the same dimension on the next lower level (recursive subdivision),

e.g., quadtree, HTINs, fractals;

In both cases operations have been defined, describing criteria for selecting spatial objects into subsets, each of which represents different hierarchical levels.

**Structural Hierarchies**. In a
structural hierarchy spatial objects are usually organized in
levels such that each level contains the same type of objects
interacting in the same way among themselves. That is, ontology
is the same for each level. The levels differ only in the degree
of detail. It is meaningful to consider hierarchies of geometric
primitives, i.e., points, lines and areas (Coffey 1981), as many
spatial concepts like Euclidean geometry, cell topology or graphs
are based on their structure, properties and relationships.
Typical examples for such hierarchies are quadtrees (Samet 1984),
HTINs (De Floriani and Puppo 1992), triacons or quaternary
triangular meshes (Dutton 1996), graph-subgraph subdivisions, or
fractals (Batty and Longley 1994).

Structural hierarchy often refers to the *granularity*
of the representation. Hernandez (1991), for example, discusses a
model for qualitative spatial reasoning using levels with
different granularity for projection and orientation (e.g.: level
0 = no orientation information; level 1 = (a) back, (b) left,
right, front; level 2 = back, front, left, right; level 3 = back,
front, left, right, left-back, right-back, left-front,
right-front). Cohn (1995) considers the problem of representing
the shape of a region, qualitatively, within a logical theory of
space. He uses just two primitive notions, that of two regions
connecting, and the convex hull of a region, to distinguish
various concave shapes. By applying the technique recursively to
the inside of a region, Cohn achieves a hierarchical
representation at varying levels of granularity. Glasgow (1995)
uses hierarchization in spatial planning. In these examples
reasoning becomes simpler on levels with fewer details.

Research on HSR involves also formal
description of functions or operations that form a hierarchy,
that is, methods to transform a nonhierarchical structure into a
hierarchical one (see section 3.1). For example, Frank and Timpf
(1994) examine the idea of the *intelligent zoom* which
implies that more details about objects become visible with the
increasing scale and restricted display view. To achieve this
zoom operation ability, they employ a hierarchical tree-like
structure to store scale-dependent representations of objects
from cartographic maps. Timpf further investigates how to link
map objects at different levels of detail that represent the same
real-world objects (1998) and proposes a hierarchical data
structure that supports and describes the behavior of map objects
at multiple levels. The hierarchical structure is a composition
of three different types of hierarchies defined according to the
functions of generalization, aggregation and filtering. The
formal specification is available as the Gofer code.

Another example comes from cognitive
linguistics and is given by Habel (1991; 1994; 1995). Habel
proposes a hierarchical system of granularity levels as an
adequate means of mental representations of space and time. He
suggests that different levels of granularity of spatial memory
are connected by specific operations such as *embedding*,
which allow for building up increasingly refined representations.
For example, mental images in spatial memory are connected
through embedding, which allows for changing of their scale. In
the case of time, the refinement operation splits the events. In
these examples a hierarchical system has proven useful as a
finite representation of a spatio-temporal continuum. Formal
logic is used to formally describe the system.

**Functional hierarchies** are
based on task decomposition. A subtask represents one level of
hierarchy. Usually each of the subtasks requires different types
of spatial objects with different interaction among them.
Consequently, each level is expected to have different ontology.
In case of functional hierarchies, a hierarchization method
usually starts with the more general task and ends at the
specific task level. This corresponds to the top-down
hierarchization method.

A multilevel highway navigation (Timpf et al. 1992) is an example of a functional hierarchy. Its conceptual model consists of the Planning level, Instructional level, and Driving level each describing a subtask in planning and navigating a journey. The most general level is the planning task that involves a highway network consisting of highways, places and interchanges. The next lower level provides sufficient instruction information for navigating such as entrances and exits. The lowest level describes the objects and actions necessary to drive a vehicle according to the instructions. The full formal specification is available in (Timpf 1992).

Another example of a functional hierarchy is Kuipers famous semantic hierarchy of robot’s movement (Kuipers and Levitt 1988; Kuipers and Byun 1991; Kuipers et al. 1993) consisting of Control, Procedural, Topological to Metric level. Each of these levels has different ontology, describing different levels of information needed to move around. For example, places, paths and regions on the topological level, linked by topological relations such as connectivity, order and containment, create a topological map of space. The same types of objects on the metrical level, linked by metric relations such as distance, direction, or shape, provide metric information for movement such as amount of rotation and travel distance. Transitions of objects and actions from one level to objects and actions on another level are described by a set of rules.

In this section we give an example in which a method of hierarchical spatial reasoning has been applied to model wayfinding in a hierarchically structured network (Car and Frank 1994; Car 1998). First we describe the design steps, and the give a brief overview of the modeling and formalization methods used.

The modeling method used here is known as conceptual modeling. Conceptual modeling is modeling of real-world situations on a higher level of abstraction, before a detailed logical and physical design takes place (Brodie, Mylopoulos and Schmidt 1984). Conceptual models provide the description of space that is closer to human conceptualization and its semantics. They communicate the formalized ideas of space and as such enhance communication between domain expert, system designer and end-user. Research on conceptual modeling, particularly developing suitable methods for specification of large, complex models requires further efforts.

A formalization method introduced here uses
object orientation as a design method, formal specifications, and
a functional programming language as a specification and
prototyping (Car and Frank 1997). The *object-oriented approach*
has been accepted as appropriate to modeling complex data
structures and hierarchically organized knowledge domains.
Software engineering proposes *object orientation* as a
design method (Khoshafian and Abnous 1990) because there is a
strong correspondence between the idea *to model both the
structure of an object and its behavior* and the way humans
build classes of similar objects according to their experience
(Lakoff 1987). The main concern of the introduction of the
object-oriented method for modeling spatial data in GIS
applications is the attempt to capture more semantics than the
existing data models do (Egenhofer and Frank 1992; Worboys 1994).
In a relational data model, for example, all data is represented
in tabular form, whereas the object-oriented model considers
complex objects as individual units with certain behavior (see,
for example, (Herring 1991; Mainguenaud 1995)).

*Formal specifications* support
object-oriented design because of their ability to describe the
structure of objects and operations applicable to them. The
formal specifications method combines the advantages of data
abstraction with an axiom-based (mathematical) method to describe
semantics (Guttag, Horowitz and Musser 1978). Denotational
semantics (Stoy 1977) show how to use mathematical methods to
describe semantics, which is a direct link to *functional
programming* (Frank and Kuhn 1995). Formal specifications and
functional programming languages are based on similar
mathematical theories and use similar syntax.

Functional programming languages (Bird and
Wadler 1988) allow to formally check specifications, and to
observe if the specifications capture the intended behavior. The
executable code is treated as a prototype. A prototype is
expected to show if the implementation is possible and if a
formal model behaves as expected. The functional language Gofer
(Jones 1994) is used as the specification language. In Gofer it
is possible to describe abstract behavior of objects, to
construct specific objects, and describes how they achieve the
intended behavior. The *code* produced by a functional
programming language is clearly readable, and allows for the
insight to be gained from reading or writing specifications.
Gofer enables specification and prototyping that are integrated
in a single and easy to use environment.

This is a contribution to the research on the development of suitable methods for specifications of large, complex systems.

The conceptual modeling method is used to model hierarchical wayfinding. The conceptual model of hierarchical wayfinding is based on the proposed theory of hierarchical spatial reasoning. The model describes the hierarchical structure of a road network and explains how the reasoning process progresses on such a structure. The tools used are graph theory, object orientation, algebraic specifications and functional programming.

According to the requirements of the hierarchical spatial reasoning, the conceptual modeling process consists of the following major steps: First, a model for the nonhierarchical case is designed. It includes a model of a road network at only one level of representation and a shortest path algorithm. Second, a hierarchical structure is introduced and a set of rules is given stating how the algorithm determines the shortest path in such a structure. In the third step results achieved by the hierarchical algorithm will be analyzed and compared to the results achieved by the nonhierarchical algorithm. In the last step the performance of the hierarchical algorithm is analyzed and compared to the performance of the nonhierarchical algorithm.

**The nonhierarchical case**. We start with specifying a generic graph
based on which a bidirectional, weighted, and hierarchical graph
are then built. As an application of it, we give a specification
of a road network for the nonhierarchical and hierarchical case.
Such graphs can then be used for the shortest path determination.
The following assumptions are made about the graph in order to
preserve the simplicity of the model:

- Nodes are situated in Euclidean space and
Euclidean distances between them can be computed.
Euclidean distance is the length of an edge. Lengths can
be generalized by weights. Such graphs are
*planar*, excluding the cases where edges cross each other. - An edge can be traversed in both ways,
therefore, the graph is considered to be
*bidirectional*.

A road network can be seen a special case of a bidirectional graph, which in turn, is a special case of a generic graph. To derive a formal model of such a road network, the generic graph has to be specified first. A road network is also a weighted graph, which requires introduction of weights.

The complete set of objects is collected and brought together into an ontology. An ontology is an abstracted, idealized model of reality containing only those objects, relations among them, and rules that govern them, which are of interest in a particular reasoning system being designed (Davis 1990). These objects, i.e., their structure and behavior, are then formalized with the help of formal specifications.

The best known algorithm for shortest paths
determination is Dijkstra’s algorithm (Dijkstra 1959). This
algorithm determines the lengths of the shortest paths between
the given node and any other node in a graph. The original
implementation of Dijkstra’s algorithm runs in *O(n*^{2}*)*
time, *n* being a number of nodes in a graph. This is the
optimal running time for a fully dense graph (i.e., a graph where
relatively few of the possible edges are missing (Sedgewick
1983)). Improvements of the running time can be achieved through
different implementations (Ahuja, Thomas L. Magnanti and Orlin
1993): e.g., using adjacency lists.

**The hierarchical case**. The
ontology for the nonhierarchical case is enriched by hierarchical
levels. A bottom-up operation based on the road classification
criterion, extracts a subgraph from the basic graph creating a
structural hierarchy. The lowest level contains the entire
network. Thus, the ontology contains the objects node, edge,
graph and level.

The *hierarchical algorithm* is a
nonhierarchical algorithm -- *Dijkstra’s algorithm*
--enriched by a set of rules how to process a hierarchical
structure. Dijkstra’s algorithm determines the shortest path
in a single level. A* set of rules* states which part of the
graph to use, when to switch between the levels, and how to
combine single-level, partial results into a complete solution.
The underlying idea of the hierarchical algorithm is the stepwise
reduction of the initial graph causing the flat algorithm to
operate on a subgraph. The improvement of the running time is,
therefore, achieved by reducing the size of the graph, and this
is enabled through the hierarchical structure of the network.

We have shown that the strategy of hierarchical subdivision of graphs improves the performance of the standard, nonhierarchical shortest path algorithm. The hierarchical algorithm is formally described, which allows to see how such algorithms are structured in general (i.e., nonhierarchical algorithm, hierarchical structure, rules to process the levels). From the formal description further properties of the hierarchical wayfinding can be derived (e.g., that wayfinding occurs in a subgraph, which in turn, corresponds to the human wayfinding).

The impact of this research on hierarchy and its use for modeling is quite large. The applied methods and results provide better insight into the theory of HSR. The major contribution to the theory is in combining advances in human knowledge and representation, and hierarchical reasoning with classical wayfinding algorithms. The theory is expected to be useful in cases where large datasets or incomplete spatial information needs processing. In-car navigation is such a case.

The method of formalization used here has proven useful, particularly to define objects in a conceptual model (i.e., their structure and operations). Gofer, as a specification tool, produced executable specification, which adds a new aspect to the formalization for the GIS purposes. Gofer-specifications were relatively easy to write and read, which was helpful in checking syntax. Executable code enabled immediate testing, i.e., prototyping; we were able observe the behavior of the model.

A formal specification of the model is available in form of a code written in the functional language Gofer and its full version can be found (Car 1997). The model was tested using theoretical data in order to test its captured behavior. Results so far confirm the validity of the conceptual model designed in this study.

Hierarchy is a powerful mechanism for dealing with complex spatial systems as it reduces the cognitive load and speeds up the reasoning process. Understanding of basic concepts of spatial hierarchies is, therefore, crucial in the design of conceptual models of space. In this paper we suggested a framework for developing concepts of spatial hierarchies and their use for spatial reasoning, which is based on the general hierarchy theory. In particular, we argued that Hierarchical Spatial Reasoning can be understood as a GeoComputation-methodology for the following reasons:

- it offers an underlying theory for modeling spatial systems using hierarchy, and explains how to do it; the result is a conceptual model of a spatial hierarchy;
- it provides a formalization method and
suggests a suitable tool;

the result is a formal specification which can be used as a prototype for testing of the model behavior.

In fact, it offers a new playground for testing the model using theoretical data first. The expected results are, for example, various parameters of the model. Once the model has been proved as valid, we can then apply it to solve real-world problems, and adjust it further if necessary.

An interesting and still open question
considers the notion of *satisficing results* produced by
hierarchical spatial reasoning. Can we measure the goodness of a
result? If so, what are the good candidates? Are they related to
a particular application, or are they application-independent?
For example, if a hierarchical algorithm is used to determine the
shortest path is in a network, a tolerance for an acceptable
difference between the optimal solution and the hierarchical one
can be a percentage of the length of the shortest edge in a graph
or of the length of an average edge size, length of a car (in-car
navigation), etc..

Another research direction is related to scale as one of the fundamental yet poorly defined concepts in Geographic Science ((Goodchild and Proctor 1997; Quattrochi and Goodchild 1997), for further information visit also http://www.ncgia.ucsb.edu/varenius/scale/). We think that hierarchy and scale are related issues, and therefore, posit a hypothesis that the basic concepts of spatial hierarchies can be used to define basic concepts of scale. This hypothesis is based on the assumption that the scale is a consequence of hierarchization (Car 1998). The idea is to analyze the existing concepts of scale following the aspects of the concepts of spatial hierarchy. The proposed framework is an analogy to the application of the general hierarchy theory to the hierarchies of space. The expected outcome is a derivation of the underlying common structure (elements and properties) of scale and its classification.

Ahuja, R. K., Thomas L. Magnanti and J. B.
Orlin (1993). __Network Flows: Theory, Algorithms, and
Applications__. Englewood Cliffs, NJ, Prentice Hall.

Batty, M. and P. Longley (1994). __Fractal
Cites: A Geometry of Form and Function__. London, Academic
Press Limited.

Bird, R. and P. Wadler (1988). __Introduction
to Functional Programming__. Hemel Hempstead (UK), Prentice
Hall International.

Brodie, M. L., J. Mylopoulos and J. W. Schmidt,
Eds. (1984). __On Conceptual Modelling__, Springer-Verlag.

Car, A. (1997). __Hierarchical Spatial
Reasoning: Theoretical Consideration and its Application to
Modeling Wayfinding__. Vienna, Austria, Dept. of
Geoinformation, Technical UniversityVienna, published Ph.D.
thesis.

Car, A. (1998). Hierarchical Wayfinding - A
Model and its Formalization. In __Geographic Information
Research: Transatlantic Perspectives__. Craglia, M. and H.
Onsrud. London, Taylor & Francis.

Car, A. (1998). Hierarchy and Scale - Research proposal. NCGIA-Varenius meeting on Scale and Detail in Cognition of Geographic Information in Santa Barbara, CA, 14-16 May 1998.

Car, A. and A. Frank (1997).
"Formalisierung konzeptioneller Modelle für GIS - Methode
und Werkzeug." __Zeitschrift für Vermessungswesen__ **122**(3):
99-114.

Car, A. and A. U. Frank (1994). __General
Principles of Hierarchical Spatial Reasoning - The Case of
Wayfinding__. Spatial Data Handling (SDH 94), Edinburgh,
Scotland, T.C. Waugh, the IGU Commission on GIS, and the
Association for Geographic Information.

Car, A. and A. U. Frank (1994). Modelling a
Hierarchy of Space Applied to Large Road Networks. In __IGIS'94:
Geographic Information Systems. International Workshop on
Advanced Research in GIS. Monte Verita, Ascona, Switzerland__.
Nievergelt, J., Thomas Roos, Hans-Jörg Scheck and P. Widmayer.
Berlin, Heidelberg, New York, Springer-Verlag. **884: **15-24.

Coffey, W. J. (1981). __Geography: Towards a
General Spatial Systems Approach__. London, New York, Methuen
Co.

Cohn, A. G. (1995). A Hierarchical
Representation of Qualitative Shape Based on Connection and
Convexity. In __Spatial Information Theory-A Theoretical Basis
for GIS__. Frank, A. U. and W. Kuhn. Berlin-Heidelberg-New
York, Springer. **988: **311-326.

Couclelis, H. and N. Gale (1986). "Space
and spaces." __Geografske Annaler__(68B): 1-12.

Davis, E. (1990). __Representations of
Commonsense Knowledge__. San Mateo, California, Morgan Kaufmann
Publishers.

De Floriani, L. and E. Puppo (1992). A
Hierarchical Triangle-Based Model for Terrain Description. In __Theories
and Methods of Spatio-Temporal Reasoning in Geographic Space__.
Frank, A. U., I. Campari and U. Formentini. Berlin Heidelberg,
Springer-Verlag. **639: **236-251.

Dibble, C. (1996). __Theory in a Complex
World: Agent-Based Simulations of Georgaphic Systems__. First
International Conference on GeoComputation, 17-19 September 1996,
Leeds, UK.

Dijkstra, E. W. (1959). "A note on two
problems in connection with graphs." __Numerische
Mathematik__(1): 269-271.

Dutton, G. (1996). "Improving location
specificity of map data - a multi-resolution, metadata-driven
approach and notion." __International Journal of
Geographical Information Systems__ **10**(3): 253-268.

Egenhofer, M. J. and A. U. Frank (1992).
"Object-Oriented Modeling for GIS." __URISA Journal__
**4**(2): 3-19.

Egenhofer, M. J. and D. M. Mark (1995). Naive
Geography. In __Spatial Information Theory-A Theoretical Basis
for GIS__. Frank, A. U. and W. Kuhn. Berlin-Heidelberg-New
York, Springer. **988: **1-15.

Fotheringam, A. S. (1992). Encoding Spatial
Information: The Evidence for Hierarchical Processing. In __Theories
and Methods of Spatio-Temporal Reasoning in Geographic Space__.
Frank, A. U., I. Campari and U. Formentini. Berlin Heidelberg,
Springer Verlag. **639: **269-287.

Frank, A. and S. Timpf (1994). "Multiple
Representations for Cartographic Objects in a Multi-Scale Tree -
An Intelligent Graphical Zoom." __Computers and Graphics,
Special Issue on Modelling and Visualization of Spatial Data in
GIS__ **18**(6): 823-829.

Frank, A. U. and W. Kuhn (1995). Specifying
Open GIS with Functional Languages. In __Advances in Spatial
Databases (SSD'95)__. Egenhofer, M. J. and J. R. Herring.
Portland, Maine, Springer-Verlag. **951: **184-195.

Frank, A. U., W. Kuhn, W. Hölbling, et al.
(1997). __Gofer as used at GeoInfo/TU Vienna__, Dept. of
Geoinformation, Technical University Vienna.

Glasgow, J. (1995). A Formalism for Model-Based
Spatial Planning. In __Spatial Information Theory-A Theoretical
Basis for GIS__. Frank, A. U. and W. Kuhn.
Berlin-Heidelberg-New York, Springer. **988: **501-518.

Golledge, R. G. (1992). Do People Understand
Spatial Concepts: The Case of First-Order Primitives. In __Theories
and Methods of Spatio-Temporal Reasoning in Geographic Space__.
Frank, A. U., I. Campari and U. Formentini. Berlin Heidelberg,
Springer-Verlag. **639: **1-21.

Goodchild, M. and J. Proctor (1997).
"Scale in a Digital Geographic World." __Geographical
& Environmental Modelling__ **1**(1): 5-23.

Guttag, J. V., E. Horowitz and D. R. Musser
(1978). The Design of Data Type Specifications. In __Current
Trends in Programming Methodology: Vol. 4 - Data Structuring__.
Yeh, R. T. Englewood Cliffs, New Jersey, Prentice-Hall, Inc.**: **60-79.

Habel, C. (1991). __Hierarchical
Representations of Spatial Knowledge: Aspects of Embedding and
Granularity__. Second International Colloquium on Cognitive
Science, San Sebastian, 7-11 May 1991.

Habel, C. (1994). Discretness, Finiteness, and
Structure of Topological Spaces. In __Topological Foundation of
Cognitive Science. Papers from the Workshop at the FISI-CS,
Buffalo, NY, July 9-10, 1994__. Eschenbach, C., C. Habel and B.
Smith. Hamburg, Graduiertenkolleg Kognitionswissenschaft
Hamburgh. **Report 37: **81-90.

Habel, C. (1995). Representing Space and Time:
Discrete, Dense or Continuous? - Is that the Question? In __Parts
and Wholes - Integrity and Granularity__. Eschenbach, C. and W.
Heydrich. Hamburg, Graduiertenkolleg Kognitionswissenschaft
Hamburgh. **Report 49: **97-107.

Hernandez, D. (1991). Relative Representation
of Spatial Knowledge: The 2-D Case. In __Cognitive and
Linguistic Aspects of Geographic Space__. Mark, D. and A.
Frank. Dordrecht, Boston, London, Kluwer Academic Press**: **373-385.

Herring, J. (1991). "TIGRIS: A data model
for an object-oriented geographic information system." __Computers
and Geosciences__ **18**: 443-452.

Hirtle, S. C. and J. Jonides (1985).
"Evidence of Hierarchies in Cognitive Maps." __Memory
& Cognition__ **13**(3): 208-217.

Jones, M. P. (1994). The Implementation of the Gofer Functional Programming System, Yale University.

Khoshafian, S. and R. Abnous (1990). __Object
Orientation - Concepts, Languages, Databases, User Interfaces__.
New York, NY, John Wiley & Sons.

Koestler, A. (1967). __The Ghost in the
Machine__. London, Pan.

Kuipers, B. and T. S. Levitt (1988).
"Navigation and Mapping in Large-Scale Space." __AI
Magazine__ **9**(2): 25 - 43.

Kuipers, B., R. Froom, W-Y. Lee, et al. (1993).
The Semantic Hierarchy in Robot Learning. In __Robot Learning__.
Connell, J. and S. Mahadevan. Dordrecht, Boston, London, Kluwer
Academic**: **1-24.

Kuipers, B. J. and Y.-T. Byun (1991). "A
robot exploration and mapping strategy based on a semantic
hierarchy of spatial representations." __Robotics and
Autonomous Systems__ **8**(8): 17.

Lakoff, G. (1987). __Women, Fire, and
Dangerous Things: What Categories Reveal About the Mind__.
Chicago, The University of Chicago Press.

Lavers, C. and R. Haines-Young (1993). Spatial
Heterogenity and New Technology. In __Landscape Ecology and GIS__.
Haines-Young, R., D. Green and S. Cousins. London, Taylor &
Francis**: **57-74.

Mainguenaud, M. (1995). "Modelling the
Network Component of Geographic Information Systems." __International
Journal of Geographical Information Systems__ **9**(6):
575-593.

Mark, D. M. and A. U. Frank (1989). __Concepts
of Space and Spatial Languages__. AUTO-CARTO 9, Ninth
International Symposium on Computer-Assisted Cartography,
Baltimore, MD, American Society for Photogrammetry and Remote
Sensing and American Congress on Surveying and Mapping.

Mark, D. M. and A. U. Frank (1996).
"Experiential and Formal Models of Space." __Environment
and Planning B: Planning and Design__ **23**: 2-24.

McNamara, T. P., J. K. Hardy and S. C. Hirtle
(1989). "Subjective Hierarchies in Spatial Memory." __Journal
of Environmental Psychology: Learning, Memory, and Cognition__ **15**(2):
211-227.

Palmer, E. S. (1977). "Hierarchical
Structure in Perceptual Representation." __Cognitive
Psychology__(9): 441-474.

Quattrochi, D. and M. Goodchild, Eds. (1997). __Scale
in Remote Sensing and GIS__. Boca Raton, CRC Press Inc., Lewis
Publishers.

Samet, H. (1984). "The Quadtree and
Related Hierarchical Data Structures." __ACM Computing
Surveys__ **16**(2): 187-260.

Sedgewick, R. (1983). __Algorithms__,
Addison-Wesley Publishing Company, Inc.

Shapiro, J., J. Waxman and D. Nir (1992).
"Level Graphs and Approximate Shortest Path
Algorithms." __Networks__ **22**: 691-717.

Simon, H. A. (1973). The Organization of
Complex Systems. In __Hierarchy Theory__. Pattee, H. New York,
Braziller**: **1-27.

Simon, H. A. (1979). Rational Choice and the
Structure in the Environment. In __Models and Thought__. **Volume
1 (Chapter 1.2): **20-28.

Stoy, J. (1977). __Denotational Semantics__.
Cambridge MA, MIT Press.

Timpf, S. (1992). __Conceptual Modelling of
Highway Navigation__. Master Thesis, University of Maine, USA,

Timpf, S. (1998). __Hierarchical Structures in
Map Series__. Ph.D. thesis, Dept. of Geoinformation, Technical
University Vienna, Vienna.

Timpf, S. and A. U. Frank (1997). Using
Hierarchical Spatial Data Structures for Hierarchical Spatial
Reasoning. In __Spatial Information Theory - A Theoretical Basis
for GIS (International Conference COSIT'97)__. Hirtle, S. C.
and A. U. Frank. Berlin-Heidelberg, Springer-Verlag. **1329: **69-83.

Timpf, S., G. S. Volta, D. W. Pollock, et al.
(1992). A Conceptual Model of Wayfinding Using Multiple Levels of
Abstraction. In __GIS - from Space to Theory: Theories and
Methods of Spatio-Temporal Reasoning__. Frank, A. U., I.
Campari and U. Formentini. Berlin Heidelberg, Springer-Verlag. **639:
**348-367.

Worboys, M. F. (1994). "Object-Oriented
Approaches to Geo-Referenced Information." __International
Journal for Geographical Information Systems__ **8**(4):
385-399.