Geoscience Reference
In-Depth Information
contiguity have been proposed. One approach is based on proximity graphs to
estimate the adjacency of points. One such graph is the Gabriel graph, in which
two nodes v i and v j are connected by an edge if and only if the disc with antipodal
points v i and v j does not contain any other node in its interior (Gross and Yellen
2003 ). A second approach to construct a contiguity graph is based on the Voronoi
diagram (Lei et al. 2012 ). Two basic units are defined to be adjacent, iff their Voronoi
cells have a common link within the smallest axis-parallel rectangle enclosing all
basic units (for a definition of Voronoi diagrams and cells see Aurenhammar et al.
2013 ). A third construction of the proximity graph is to start with a complete graph
and then sequentially go over all edges and delete for two intersecting edges in the
planar representation of the graph the longer or more costly one (Haugland et al.
2007 ). All three graphs are planar. Moreover, by definition the Gabriel graph is a
subset of the Voronoi-based graph.
Example 23.1 An example for these three proximity graphs for a point set with
26 basic units is depicted in Fig. 23.2 . The Gabriel graph defines the most strict
neighborhood relation. The graphs obtained by Lei et al. ( 2012 ) and Haugland et al.
( 2007 ) are fairly similar. The main difference is that the latter typically establishes
more adjacencies along the boundary of the convex hull of the point set. Just by
looking at the graphs it is difficult to decide which one is more suitable.
a
b
c
d
Fig. 23.2 Three different approximate contiguity graphs. ( a ) Point set of basic units. ( b ) Gabriel
graph. ( c ) Voronoi-based graph. ( d ) Non-crossing edges graph
 
Search WWH ::




Custom Search