380
M. Weber and E. A. Lee
Fig. 5 Another example of logical inference for anti-proximity
A relational ontology of distance for a Euclidean space permits more sophisticated
inference methods. A considerable amount of research has been undertaken in the
sensor network community to find a Euclidean space embedding for a weighted
undirected graph such that the Euclidean distances between nodes in the embedding
match the edge weights in the graph. If such an embedding is successfully found, it
is possible to infer internode distances not explicitly specified. One such algorithm
[24] uses a process of iterative trilateration with robust quadrilaterals where three
nodes with known Euclidean position (say A, B, and C) are used to establish the
position of a connected node (D). Once the position of D is established, it can be
used in the next iteration of the algorithm as a reference point to give the position of
some other node E.
In addition to determining unknown inter-node distances, the properties of a
Euclidean space also facilitate detection of inconsistent edges signifying outlier
measurements. In prior work, [25] we expanded upon an algorithm given in [26]
which uses graph rigidity theory to identify components of a graph that admit only a
specific embedding. If a questionable edge is wildly inaccurate, it can be identified
by considering other rigid subgraphs that are consistent with Euclidean geometry.
These sorts of Qualitative Spatial Reasoning (QSR) received significant research
attention in the 1990s. The main focus of this work was the construction of formal
algebras for inference on qualitative spatial relationships. For example, Frank’s
calculus for cardinal directions and informal distances such as “near” and “far” can
infer such relationships for unknown cities given knowledge on how they are related
to a known city network [27]. Arguably, the most notable outcome of QSR today is
the Region Connection Calculus (RCC) for 2-dimensional mereology (the part whole
M. Weber and E. A. Lee
Fig. 5 Another example of logical inference for anti-proximity
A relational ontology of distance for a Euclidean space permits more sophisticated
inference methods. A considerable amount of research has been undertaken in the
sensor network community to find a Euclidean space embedding for a weighted
undirected graph such that the Euclidean distances between nodes in the embedding
match the edge weights in the graph. If such an embedding is successfully found, it
is possible to infer internode distances not explicitly specified. One such algorithm
[24] uses a process of iterative trilateration with robust quadrilaterals where three
nodes with known Euclidean position (say A, B, and C) are used to establish the
position of a connected node (D). Once the position of D is established, it can be
used in the next iteration of the algorithm as a reference point to give the position of
some other node E.
In addition to determining unknown inter-node distances, the properties of a
Euclidean space also facilitate detection of inconsistent edges signifying outlier
measurements. In prior work, [25] we expanded upon an algorithm given in [26]
which uses graph rigidity theory to identify components of a graph that admit only a
specific embedding. If a questionable edge is wildly inaccurate, it can be identified
by considering other rigid subgraphs that are consistent with Euclidean geometry.
These sorts of Qualitative Spatial Reasoning (QSR) received significant research
attention in the 1990s. The main focus of this work was the construction of formal
algebras for inference on qualitative spatial relationships. For example, Frank’s
calculus for cardinal directions and informal distances such as “near” and “far” can
infer such relationships for unknown cities given knowledge on how they are related
to a known city network [27]. Arguably, the most notable outcome of QSR today is
the Region Connection Calculus (RCC) for 2-dimensional mereology (the part whole