Spatial Relation Abstract in Map Generalization Process
Tinghua  Ai               Peter van Oosterom
Section GIS Technology  , Department of Geodesy
Faculty of Civil Engineering and Geoscience,
Delft University of Technology, the Netherlands
a.tinghua@geo.tudelft.nl,         oosterom@geo.tudelft.nl

Abstract  From the point of view of mapping transformation, this  paper presents a map generalization concept framework which regards generalization as two kinds of  mapping procedures: spatial entity mapping and spatial relation mapping. According to the number change of participating entity, spatial entity mapping is classified as 1-1, n-1, n-n mapping. And spatial relation mapping is described as a composite relation transformation of topological, distance and orientation relation. The concept spatial relation resolution is introduced  to describe spatial relation related constraints. Based on 9 intersection model, cardinal direction model and iso-distance-relation model, the paper gives three sorts of relation resolution representation for topologicl, orientation and distance relation respectively. The behavior of two mapping in map generalization is discussed and spatial relation abstract obtains emphasis compared with traditional generalization concept model.

Keywords map generalization, spatial relation, spatial relation resolution.

1.	Introduction

The questions of what  map generalization process is and how to describe the process are basic issues in the research field of generalization concept model. From different perspectives, related research gives various answers and correspondingly yields different solutions in operator classifying, constraint analysis, workflow control, and generalized result evaluation.  Based on the idea of “processing based on understanding”, Brassel  and Weibel (1988) gave a description dividing the map generalization into five steps: structure recognition, process recognition, process modeling, process execution, and data visualization. Supported by information theory, generalization could be considered as a process of information entropy transformation (Bjorke 1996, weber 1980). According to this understanding, the original map is information sender and the generalized map is information receiver. The generalization reflects as the communication process of information coding and decoding with entropy reduction due to noise impact.  From artificial intelligence viewpoint, generalization could be regarded as a problem solution process (Ware and Jones 1998, Longergan 1999) to find the best solution from multiple candidates under the control of geometric, topological and semantic constraints. Some methods in AI and expert system field such as simulated annealing technology, hill climbing technology can be used in such as displacement decision, object selection(Ware and Jones 1998).  As a complex processing system, map generalization involves multiple hierarchical analysis and multiple operation execution. Ruas and others think of generalization an agent action process and try to use agent method which is capable of controlling its own decision making and acting to resolve the problems in this complex system (Lamy, Ruas, Mackness 2000). 
Supported by different theories and technologies, one understanding of generalization process is able to solve some special problems and has advantages in some aspects over others. It is difficult and also not necessary to decide which generalization concept model is the best one. What we are interested is the completeness degree of problem solution for one understanding and usually integrated methods based on two or more understandings are required to solve one question in generalization. In this field, one important trend is that the concept model requires to get formalization representation and then allow computer to understand and realize the process through data model and algorithm design.  Based on the set mapping theory in relation algebra subject, we will present a map generalization concept model which regards generalization as two kinds of mapping procedures: spatial entity mapping and spatial relation mapping. An outstanding nature in this model is the introduction of spatial relation abstract. Traditionally the considered object in generalization focuses on spatial entity and most of generalization operators are entity oriented.   
Map generalization can be separated as database generalization and visualization generalization (Brassel and Weibel 1988, Mcmaster and Shea 1991, Peng 1995, Muller 1991). The previous process focuses on data content abstract from the point of view of lower resolution without consideration of data visualization. While the later deals with such as graphic conflicts when spatial object is represented as a symbol. The concept model in this paper concerns with the previous generalization and considers the map database a set containing spatial, attribute and temporal information.
The rest of paper is organized as follows. Section 1 presents the generalization concept model which is based on mapping transformation. Concepts spatial relation resolution and spatial relation abstract are discussed in section 2. How two mapping procedures behavior in the generalization is arranged in section 3. Some future works are presented in conclusion, section 4.

1. Map generalization concept model based on mapping transformation.

Map database contains two categories of information: spatial entity and spatial entity relationship. The original map can be represented as entity set Eoriginal ={ eoriginal } and relation set  Roriginal = { r | r ∈Eoriginal ×Eoriginal }. The generalized new map can be represented as entity set Enew ={ enew } and relation set  Rnew = { r | r ∈Enew ×Enew }( Wu 1997).  The mapping transformation from set Eoriginal , Roriginal  to Enew , Rnew carries out  the map generalization process. This is the basic idea of  map generalization concept model based on set mapping. The detailed discussion is presented as follows.

orientationmapping O 

distance mapping D

m [<б2 , τ2>]

m [<б1 , τ1>]

conflict displacement
adjacent conversion
neighbor consistent adjustment
……

topologicalmapping T

point cluster simplification
polygon cluster grouping
network simplification
……

aggregation
combination
link
super-grouping
……

simplification
exaggeration
collapse
attribute change
……

mapping n-n f3

mapping n-1 f2

mapping 1-1
f1

spatial relation mapping  g: R1→R2

spatial entity mapping  f: E1→E2

Figure 1. Map generalization concept model based on set mapping principles

Gen [ε1，ε2]

classified as

compounded by

Each map M  contains sets E and R representing  real space under the certain abstract degree variableε, which depicts  map representation resolution.  State variable ε may be described as two-element tuple (We do not consider temporal information here)ε：(б，τ), whereб,τ stands for spatial resolution and attribute resolution respectively. Usingε1<ε2  represents abstract degree ε1 (corresponding to detailed map) less thanε2 (corresponding to simple map).  Then the original map M[ε1]is represented as:
M[ε1]= M [<б1, τ1>] :  E1∪R1
The generalized map M[ε2] is represented as:
M[ε2]= M [<б2, τ2>] :  E2∪R2  ,    Whereε1<ε2  
The generalization mapping can be represented as:
Gen [ε1，ε2]：m[ε1] → m[ε2].
Mapping Gen can be separated as spatial entity mapping f: E1→E2 , and spatial relation mapping   g:  R1→R2. For spatial entity mapping f , based on the number change from original element to image element we can divide it into three classes:
              1-1 mapping:   e’= f1(e);
n-1 mapping : e’= f2(e1, e2, … ei)
n-n  mapping : (e’1, e’2, … e’j) = f3 (e1, e2, … ei),  where ei  the spatial entity.
For spatial relation mapping g, based on spatial relation classification ( Egenhofer 1991) we can consider it as the composite mapping of three independent spatial relation mapping: topological relation mapping T, distance relation mapping D and orientation  relation mapping O.  There exists following representation: r’= g (r) = TDO (r)  , where r the spatial relation. This generalization concept model may be depicted as figure 1
Spatial entity mapping and spatial relation mapping change information in cartographic database and contain sorts of transformation form. But for generalization, there is determinate transformation trend which is from high resolution to low resolution. In this sense, map generalization can be regarded as a special spatial mapping, an abstract procedure.  

   1-1 mapping                     n-1 mapping                        n-n mapping
Figure 2, Illustrations of three kinds of spatial entity mapping

Spatial entity mapping involves spatial information transformation and attribute information transformation respectively controlled under spatial resolutionбand attribute resolutionτ.  For 1-1 mapping  f1 , the mapped entity is the same as original one but having different properties in geometric and semantic representation.          If  f1(e )=NULL, it means spatial entity e removed from database, otherwise the image entity f1(e ) still exists independently but with nature change, which may be the simplification of geometric shape, exaggeration of size to enhance existence, collapse conversion from polygon to skeleton line or collapse from polygon to center point, etc.  For n-1 mapping f2 , the original entity does not remain independent and complete, just acting as a composite part of new mapped entity. This mapping reflects as object combination. According to two hierarchical structure relations between basic elements and aggregated object, Is_A and Part_of, the mapping can be further separated into aggregation of homogeneous spatial entities  and amalgamation  of heterogeneous spatial entities. In this mapping, both  spatial adjacency and semantic adjacency have to be taken into account. For example, in land-use parcel aggregation, when parcels have similar spatial distance to each other, those with closer relation in semantic hierarchical tree prefer to be aggregated firstly. For n-n mapping, it is cluster object oriented. The elements before and after mapping remain independent and complete, but as they are highly related to each other in spatial or semantic aspects, the cluster structure characteristics among them, such as spatial distribution, Gestalt nature, terrain landform feature, becomes the key consideration in the mapping,. From the point of view of composite object, this kind of mapping can be thought of as 1-1 mapping of composite object, since entities participating mapping procedure make up a composite object. Considering the same level of mapping object, the call of n-n mapping is more reasonable.  The examples of this mapping could be resample of resident point cluster, simplification of polygon cluster such as island, lake, building, etc., generalization of road network, simplification of street network and street block, abstract of river drainage and abstract of terrain contour, etc. 
2. Spatial relation resolution and spatial relation abstract  

According to relation algebra definition, spatial relation is described as Cartesian tuple of spatial entities. So the execution object in spatial relation mapping is spatial entity pair rather than spatial entity itself. It is different from the transformation of geometric space, such as affine transformation, which is entity itself oriented. The expression e1 r e2 denotes spatial entity  e1  having relation r with entity e2 . The mapping that original relation r is mapped as r’  between e1 and  e2  can be represented as follows:
e1 r’ e2 = g (e1 r e2)
three basic spatial relationships have independent semantic descriptions, but how to combine them to get an integrated description for spatial cognition has not resolved by now. So we can not find the mathematics function of mapping g just like affine transformation which can be represented as one matrix to integrate three independent transformations, movement, rotation and scaling.  For spatial relation representation, are topological, orientation, distance relation really basic relation elements ? Is there other relation need to be added ?  Although spatial relation research meets challenges, we can give qualitative discussions for spatial relation mapping. 
Unlike general spatial relation mapping, the relation mapping contained in generalization is the transformation from detailed state to abstract state.  In this sense, we call it spatial relation abstract. Displacement operation is a typical spatial relation mapping in generalization, through entity position adjustment to resolve spatial relation conflict. In this procedure the operated object is spatial entity pair rather than independent entity. 

 (A close B)→ (A’ zero distance  B’)
 (A close C) → (A’ far  C’)
 (B close C) →  (B’   far  C’)

 (A NorthWest B)→ (A’ North B’)
 (A West C) → (A’ SouthWest  C’)
 (B SouthWest C)→ (B’ SouthWest C’)

 (A disjoint B) → (A’ touch  B’)
 (A disjoint C) →(A’ disjoint C’)
 (B disjoint C) → (B’ disjoint C’)

topological mapping                     orientation mapping                          distance mapping
Figure 3, An illustration of spatial relation mapping

For map state representation, we have spatial resolutionб，attribute resolutionτ as well as temporal resolution. Peng(1995) classified spatial resolution as spatial size resolution, spatial feature resolution and spatial distance resolution.  These resolutions aim at spatial entity abstract operation. Spatial relation abstract is also based on resolution change, so a new resolution concept, spatial relation resolution requires to be built. Spatial relation resolution (abbreviated as SRR later) is defined as the minimum identifiable semantic description of spatial relation. Spatial relation representation, including topological, orientation and distance relation, has different similarity to each other. It means some relations are close to each other while others far. The close relations can be further grouped as a higher level semantic description. So the spatial relation description is a hierarchical tree structure, and the SRR describes the hierarchical level, represented as the node depth in tree structure. SRR description depends on the model of spatial relation representation. Next we will give three methods of constructing relation hierarchical tree for topological, distance and orientation relation respectively.  

2.1 Topological relation resolution

Figure 4, 19 topological relations between line and area object (left) can be mapped as 4 descriptions (right) with resolution decrease.(Left graphic is from Egenhofer 1992) 

Nine intersection representation of topological relation (Egenhofer 1991,1995) can get 29=512 sorts of relation between two spatial objects.  The valid relation is less than this number after meaningless relations removed.  Among the remained relations, according to steps of changing one state to another state, Egenhofer and Marc (1995) built the conceptual neighbor of topological relation. The connection between neighbor representation obtains a network to describe adjacent relation of topological relation (note the saying relation of relation), as shown in Figure 4 left.  In this model, the less changing steps from one relation to another relation, the closer similarity between them is. Based on this model, we can construct the hierarchical tree to represent semantic level of  topological relation. According to certain cognition standards, some neighbor relations in the neighbor network are grouped into high level description. As shown in figure 4, original 19 relations between line and area can be grouped as 4 high level relations: inside, outside, go across and on boundary.  Within each group, the relation element is no longer to be distinguished to each other under lower resolution standard. For some purpose, 4 distinguished relation representation is enough and under control of this resolution we can execute spatial relation mapping to get abstract representation.    

Figure 5,   Building polygon cluster and Voronoi diagram partitioning

A

b

 2.2 Distance relation resolution
Compared with topological relation research, distance relation representation is less active and has fewer achievements in qualitative description. Absolute quantitative representation of how far between two objects is able to use Euclidean   distance.  But in distance relation representation, what it means  for A to be near B depends not only on their absolute positions(and the metric distance between them), but also on their relative sizes and shapes, the position of other objects, the frame of reference (Hernandez and Clementini, 1995). The context environment plays an important role in distance relation representation. Next we present a method based on Voronoi diagram (VD) to represent distance representation, and based on this representation discuss distance relation resolution. 

Figure 6,  Iso-distance-relation contour referenced with center object A, left with interval adjacent degree value 1 unit and right with 2 unit.

A

A

b

b

Figure 7,  Iso-distance-relation contour referenced with boundary b, left with interval adjacent degree value 1 unit and right with 2 unit.

Each spatial entity in scene environment has a certain influence region surrounding it and the distribution of influence region has to consider the existence of neighbor objects.  Assuming the space is isotropic, then we can use Voronoi diagram partitioning area acting as spatial entity influence region. The boundary of VD cell polygon equally partitions two neighbor left/right entities. The VD partitioning can be thought of  the result of each entity equally competing outward for growth range.   If two VD cells share common boundary, we can say two entities respectively  related to cell polygons  are adjacent, even their metric distance is far. This is because there is not the third object locating between them, otherwise there will be not shared boundary between them.  Based on this idea, we can apply relation between VD cells to represent distance relation between spatial entities.  Making use of the adjacent transmitting property, we define a variable adjacent degree to describe distance relationship and use next algorithm to obtain value adjacent degree of all objects referenced with object A.

1>   Let A itself adjacent degree 0, and initiate other object adjacent degree -1; 
2>  Initiate A belonging to active object set, Initiate variable degree_count 0;
3>  Repeat next steps until active object set NULL;
3.1>   Find all adjacent objects of active object set based on VD cell extending search;
3.2>   Remove those adjacent objects with adjacent degree rather than –1 and get valid adjacent objects;
3.3>   degree_count add 1 and assign the value into each valid adjacent object;
3.4>   Empty active object set  and let valid adjacent objects belonging to active object set;

Next we select and connect part of VD cell boundaries getting the contour line which separates  object with adjacent degree n from those with adjacent degree n+1, getting the result as shown in figure 6 left. The objects within the loop between two neighbor contour lines have the same adjacent degree with referenced object A. So we call this kind of contour line the iso-distance-relation contour just like altitude contour of terrain representation. The smaller value of adjacent degree is, the closer distance relation two objects has to each otheris. Obviously this contour is different from the iso-distance contour which is represented as progressive circle buffers with the same center and increasing radius. The iso-distance-relation model considers the context environment and spatial distribution. The object far away in metric distance has possibly very low adjacent degree and close distance relation with referenced object. The referenced object could be object set rather than one, for example, the objects adjacent to outside boundary as shown in figure 7. 
Having the iso-distance-relation model, we can now discuss the distance relation resolution. In terrain contour representation, we use interval altitude expressing resolution, the smaller interval altitude, the higher resolution.  In the same way, we adopt the interval adjacent degree describing the distance relation resolution. Selecting one from every two neighbor contour lines gets the distance relation representation whose resolution reduces half as shown in figure 6 right and figure 7 right. Higher resolution corresponds to more grades in distance relation representation. For example in the representation of 1 unit interval adjacent degree we use following semantic expression containing 6 grades:
( very very close, very close, close, medium, far, very far, very very far) 
But for the representation of 2 unit interval adjacent degree, the relations will be grouped into   updated semantic description with such as following 3 grades:   (close, medium, far ). 
Based on this model, if the object moves within loop, it does not destroy the constraint of distance relation with reference object and when considering distance relation only, it is not necessary to execute relation mapping to correct distance relation. But if the object moves across loop, the distance relation mapping is required to correct destroyed distance relation.  The lower resolution is, the wider loop exists and the chances of destroying original relation are fewer.  For how resolution impacts mapping generalization, we will discuss in section 3.

2.3 Orientation relation resolution
Frank(1992,1996) presented two methods of cardinal orientation direction representation, one based on triangular areas and another based on projection. Here we give the representation of orientation relation resolution based on this cardinal direction model. The semantic description of cardinal direction  has hierarchical properties. We have 4 distinguished direction relations: north, west, south, east with each covering 2π/4  sector range. Further separating, we can get 8 direction relations: north, northeast, east, southeast, south, southwest, west, northwest with each covering 2π/8 sector range. The separation can go on and get more detailed direction relation descriptions. The angle range of one direction covering is able to be defined as orientation relation resolution. 

3.	Spatial relation abstract behavior in map generalization

The reason of generalization execution exists in the representation against constraints and so an abstract processing is needed to adjust it.  The constraints of generalization are usually the statements related to spatial, attribute and temporal resolution. Weibel and Dutton(1998) gave 4 types of distinguished constraints: graphical, topological, structural, and Gestalt. From the point of view of mapping transformation, the constraints can be categorized as spatial entity associated constraints and spatial relation associated constraints. The latter relates to not only topological relation which appears in Weibel and Dutton’s classification but also distance relation, orientation relation, and its statement format usually reflects as “ remaining spatial relation unchanged ” or “avoiding the appearance of undistinguishable relation ”. The comparison of spatial relation equality has to be based on SRR just like the equality judgement between two float numbers, in which consideration precision should be predefined. Under certain resolution, according to the category of destroyed constraints, corresponding spatial entity mapping and spatial relation mapping is required to execute. From one state to another state during map generalization, the relation between spatial entities  must have changed in strict sense. But under a low resolution, the cognition neglects most of weak changes thinking they remain original state. Only for those distinct relation change, the post-process is required to adjust the spatial position and the post-process is usually called displacement in traditional map generalization. Based on spatial mapping model in this paper, displacement is just one of concrete forms of spatial relation mapping. In this section we will focus on spatial relation mapping and give three cases of behavior in  generalization. 
Firstly we present some algebra denotations.  In map generalization algebra system  <E, R, E’,R’, f, g>,  E, R, E’, R’ respectively denotes spatial entity set, spatial relation set of original map, and spatial entity set , spatial relation set of new map.   f, g denotes spatial entity mapping and spatial relation mapping respectively.  For two original entities ei, ej  E, there is relation rR, ei r ej . After next mapping eif(ei)E’, ejf(ej) E’,  the new mapped entities have new relation r’R’,     f(ei) r’ (ej).  The spatial relation mapping: ei r ejg( ei r ej )= ei r’ ej  carries out the relation conversion from r to r’.   

3.1	Spatial entity against constraint

No entity  mapping, Require mapping g:
  g(ei r’ej)    ei r ej

eif(ei), ejf(ej), f(ei)r’ f(ej)≠ ei r ej
Require relation mapping  g :
g( f(ei)r’ f(ej) )    f(ei)r f(ej)

eif(ei), ejf(ej),
 f(ei) r’ f(ej) = ei r ej
No relation mapping  g  

f

f

g

g

Spatial entity representation destroys the constraints associated with such as size resolution, feature resolution or attribute class resolution. Spatial entity mapping f  is required to abstract and get simple representation which respects resolution requirements. If  the spatial relation r’ between abstracted entities  equals to original r ,  f(ei)r’ f(ej)= ei r ej, and the relation r or r’ is not against relation constraint, then relation mapping is not necessary, just as shown in Figure 8 A. Otherwise f(ei)r’ f(ej)≠ ei r ej, it means that the constraint “remaining original spatial relation” is destroyed, and the relation mapping g is required to convert r’ to r, just like the example in Figure 8 B, in which relation mapping g corrects overlap relation between two simplified buildings returning to original relation touch.

A                                                                 B                                                             C
Figure 8.  Behaviors of two mappings in map generalization

3.2	Spatial relation against constraint
Spatial entity satisfies constraint of independent representation, but the relation representation of entity pair has the problem of too detailed to be distinguished. Then spatial relation abstract g is needed.  As shown in figure 8 C, when resolution reduced, many detailed distance relations need to be assigned to high level representation selecting a typical representative from low relations, and here too short distance within object edge has to be assigned to zero distance, g(eir’ej)  eirej. The street generalization of classifying street into  grades according to street width belongs to this case. Changing each polygon of lake cluster from disjoint to exactly touch also belongs to spatial relation mapping. What drives the map generalization is the relation constraint rather than entity constraint. For this kind of mapping, some of them can be explained as operation displacement just like figure 8 C, but others such as street classification generalization and lake cluster generalization are not able to be described as displacement. From the the classification of 20 generalization operators which is presented by Mackness(1994)  or 12 operators  classified by Shea & Mcmaster(1989), it is difficult to find a proper operator to explain this kind of generalization. The reason is that the operator classification only considers entity oriented operation, neglecting the relation operation. 
In  spatial relation mapping, SRR plays the main role. For figure 7 which represents building cluster within a street block, when street widened, the boundary b moves and destroys the relation between street edge and neighbor buildings. How far away the moving b impacts and how strong degree it impacts for different regions depends on SRR consideration, adjacent degree. Based on iso-distance-relation model, the displacement problem between street edge and buildings could be resolved through  adjacent degree loop analysis and the concept field in physics science could be borrowed. The iso-distance-relation contour is similar to isodynamic of magnetic field. For detailed discussion of this question, we will present a special paper.  

3.3	Both spatial entity and spatial relation against constraints
This is the mixture of two former cases. The relation mapping has to take into account constraints from two sources, one the destroyed original relation possibly resulted from entity mapping, another the undistinguished relations in existing relation representation. Generally spatial entity mapping f executes firstly, then  the relation mapping  g( f(ei)r’ f(ej) )    f(ei)r f(ej) on the one hand performs relation abstract, on the other hand corrects the damaged relation. Sometimes, relation abstract implicitly has satisfied the constraint “retaining relation unchanged ” under low resolution recognition. This process contains two comparisons, one the parallel state between neighbors, another the historical state between after mapping and before mapping.

4.	Conclusion 

Based on algebra mapping theory and according to two categories of information contained in cartographic database, this paper presents a new map generalization model in which spatial relation generalization gets much emphasis compared with traditional ones. This model provides generalization with a standard framwork on how to classify generalization operators, which is an argument question in this field.  Recently the research of spatial relation computation and reasoning based on certain model of spatial relation representation, such as 9 intersection model is active in GIS community. As a special relation operation，spatial relation abstract in map generalization  has to consider an important concept, spatial relation resolution, and this paper based on Egenhofer’s concept neighbor of 9 intersection model, Frank’s cardinal direction model and our iso-distance-relation model respectively discusses the resolution construction for topological, orientation and distance relation.    The future works involve to:
1>	Further formalize the generalization concept model and separate spatial entity mapping, spatial relation mapping deeply according to different constraints to construct a detailed formalized generalization operator classification system.
2>	Develop the integrated representation of three sorts of spatial relation aiming at relation resolution change in map generalization.
3>	Build methods to detect spatial representation conflicts based on spatial relation evaluation and apply relation mapping approach to resolve conflicts in generalization.

References

[1] Bjorke,J. T. Framework for Entroy-based Map Evaluation, Cartography and Geographic Information systems, 23(2):78-95,1996.
[2] Brassel, K. E. and Weibel, R. A Review and Framework of Automated Map Generalization, Int. Journal of Geographical Information Systems, 2(3): 229-244, 1988.
[3] Clementini, E., Sharma, J. and Egenhofer,M. Modeling Topological Spatial Relations: Strategies for Query Processing, Computers and Graphics, 18 (6): 815-822, 1994.
[4] Egenhofer, M. J. and Mark, D. Modeling Conceptual Neighborhoods of Topological Line-Region Relations, International Journal of Geographical Information Systems, 9 (5): 555-565, 1995.
[5] Egenhofer, M. J. and Franzosa, R.D. On the Equivalence of Topological Relations, International Journal of Geographical Information Systems, 9 (2): 133-152, 1995. 
[6] Egenhofer,M.J. and Franzosa, R. D. Point Set Topological Spatial Relations, International Journal of of Geographical Information Systems, 5(2):161-174,  April-June, 1991.
[7] Frank, A.U. Qualitative Spatial Reasoning: Cardinal Directions as an Example, International Journal of Geographical Information Systems, 10 (3): 269-290,1996.
[8] Frank, A.U. Qualitative Spatial Reasoning about Distances and Directions in Geographic Space, Journal of Visual Languages and Computing, 3: 343-371, 1992. 
[9] Goodchild, M .F. Egenhofer, M., Kemp, M., Mark, D. ,Sheppard.E. Introduction to the Varenius Project, International Journal of Geographical Information Science, 13(8): 731-745, 1999.
[10] Hernandez, D. and Clementini, E.: Qualitative Distance, Proceedings of COSIT’95, Semmering, Austria: 45-57, 1995.
[11] Lonergan, M. E., Jones, C. B. and Ware, J. M. Optimal Map Generalization: Saving Time with Appropriate Measures of Imperfection, CD-Rom Proceedings 19th Int. Cartographic Conference, Section 8,  Ottawa,1999.
[12] Lamy, S., Ruas, A., Demazeau, Y., Jackson, M., Mackaness, W., and Weibel, R. The Application of Agents in Automated Map Generalization, CD-Rom Proceedings 19th Int. Cartographic Conference, Ottawa, 1999. 
[13] Mackness, W. An Algorithm for Conflict Identification and Feature Displacement in Automated Map generalization, Cartography and GIS: 21(4), 1994.
[14] McMaster,R. and Shea,S. Cartographic Generalization in Digital Environment: When and How to Generalize, Proceedings  AUTOCARTO 9, 1989.
[15] Muller, J. C., Lagrange, J.-P. and Weibel, R. (eds.):  GIS and Generalization: Methodology and Practice. London: Taylor & Francis,1995. [16] Oosterom, P. van, The GAP-tree, An Approach to On-the-Fly Map Generalization of An Area Partitioning, in Muller,J-C., Lagrange, J-P., Weibel, R. GIS and Generalization: Methodology and Practice. Taylor & Francis, London,120-132, 1995.
[17] Peng, W.  Automatic Generalization in GIS,  ITC Publication Series (The Netherlands)，1995.
[18] Ruas,A. A Method for Building Displacement in Automated Map Generalization, International Journal of Geographic Information Science, 12(8):789-803,1998.
[19] Ruas, A., Mackness W. Strategies for Urban Map Generalization, Proceedings of the 18th International Cartographic Conference, Stockholm, vol.3: 1387-1394,1997.
[20] Ware, J. M. and Jones, C. B. Conflict Reduction in Map Generalization Using Iterative Improvement, Geoinfomatica, 2(4): 383-407,1998.
[21] Weber,W. Map Generalization---An Information Science Approach,In: Opheim, H. ed. Contributions to Map Generalization Proceedings, Oslo, Norway: Norweigian Computing Center, pp. 31-52, 1980.
[22] Weibel, R. and Dutton, G.H.  Constraint-Based Automated Map Generalization. Proceedings of the 8 th Interna-tional Symposium on Spatial Data Handling, Vancouver, BC, pp. 214-244, 1998.
[23] Worboys, M.F., Metrics and Topologies for Geographic Space, in Advances in Geographic Information Systems Research II: Proceedings of the International Symposium on Spatial Data Handling, Delft, Kraak, M.J. and Molenaar, M. (eds.), Taylor & Francis, pp. 365-376, 1996. 
[24] Wu, H. H. Structured Approach to Implementing Automatic Cartographic Generalization, Proceedings of the 18th ICC, Stockholm, Sweden， Vol.1: 349-356, 1997.