A Strategy for Drawing a Conceptual Neighborhood Graph
SchematicallyUniversität
BremenYohei Kurata
SFB/TR 8 Spatial Cognition, Universität Bremen / ykurata@informatik.uni-bremen.deMotivation

Research Goal
To propose a strategy for arranging spatial relations
in a CNG such that the CNG becomes schematic

Conceptual Neighborhood Graph [1] (CNG) is a diagram in which
spatial/temporal relations are networked based on their similarity.
Well-designed CNGs highlight the symmetric structures of the relation set
and, therefore, they are useful for schematizing the relations.

This problem is essentially to optimize the spatial arrangement of relations
in a graph under the following criteria:•to place the symmetric relations at symmetric locations•to avoid the crossing of links as much as possible•if possible, to draw the graph in a two-dimensional planee.g., A CNG for 13 temporal relations [1]Note:
We use the 9+-intersection[1] for modeling spatial relations (topological relations),by which the relations are distinguished by the patterns of icons

However, how to design such schematic CNGs is not well discussed
except the definitions of ‘neighbors’.

’s’s’s’sinteriorInterior

boundary

start point
end point

exterior

exterior

Proposed Strategy
Example 1:

Example 2:

Relations between Two Regions in a Sphere

Relations between a Line and a Region in a Plane
Step 1

Determine the ‘neighbors’ (links) among the given set of relations R basedon the similarity

Step 2

C1:
C2:’s interior and exterior’s interior and exterior

C1:
C2:

Decide one or two ‘symmetry concepts’ Ci’s direction’s interior and exterior

Step 3yy

For each Ci, identify R’s subset Ri that is self-symmetric with respect to Ci.
Then, among the relations in I Ri, identify the relation r* that has the largest
number of neighbors, and place r* at (0, 0, 0).

r*x

R1¥{r*} = φR2¥{r*} = φr*

Step 4xLocate the relations in R1¥{r*} on the x-axis at (a, 0, 0) (a∈Z), such that thelength of each link becomes two. Leave the relations that have no link withthe other relations in R1.
In a similar way, locate the relations in R2¥{r*} on the y-axis.

R2¥{r*} = φ: unlocatedy
Step 5xyLocate all remaining relations at (a, b, 0) (a, b∈Z) successively, such that:- each relation is located at equal distance from its neighbors, wheneverpossible;- the remaining relations in R1 and R2 are located on the x- and y- axes,respectively; and- pairs of symmetric relations with respect to C1 and C2 are locatedsymmetrically with respect to x- and y-axes, respectively.

aboutxzzy

Step 6yIf two or more relations are placed at the same locatrion, then relocate eachof them from (a, b, 0) to (a, b, c) (c ∈Z), such that the links do not intersectwith each other and the total length of the links becomes the smallest
Flip the left halfxx
Step 7
Rotate the righthalf by 180°

If preferable, simplify the CNG by continuous transformation

View from the bottom

The CNG developed by
Egenhofer [2]

The CNG developed by
Kurata and Egenhofer [3]Future Work• To examine the applicability of the proposed strategy to more
complicated topological relations and other sorts of spatial relations

References• To fully automate the above process[3] Kurata & Egenhofer (2007) The 9+-Intersection for Topological Relations between a DirectedLine Segment and a Region. Workshop on Behavioral Monitoring and Interpretation, 62-76[1] Freksa (1992) Temporal Reasoning Based on Semi-Intervals. Artificial Intelligence 54, 199-227[2] Egenhofer (2005) Spherical Topological Relations. Journal on Data Semantics III, 25-49