CD-graph: planar graph representation for spatial adjacency and neighbourhood relation with constraints

Abstract

Neighbourhood relational graphs are widely used in Geosciences. Given a set of spatial objects (vertices) in the plane together with a set of spatial obstacles and spatial facilitators in straight-line edges, the constrained Delaunay graph (CD-graph) is an undirected graph representing the spatial adjacency and neighbourhood relation of objects. CD-graph is an approximated triangulation of vertices with the following properties: (1) the obstacles are included in the graph as some barrier edges that block the connection of the objects on both sides of the obstacles, and the facilitators are included in the graph as some nontrivial edges that connect the objects that are broken by the obstacles; (2) it is as close as possible to the Delaunay triangulation (D-TIN). CD-graph can be used to represent the spatial adjacency and neighbourhood relation of objects with constraints. A theoretical contrast is conducted to differentiate CD-graph, arbitrary (unconstrained) D-TIN and constrained D-TIN. Meanwhile, a two-step constraint-embedding algorithm is proposed to build CD-graph in optimal time by using divide-and-conquer technique. Subsequently, the Voronoi diagram and D-TIN-based k-order neighbours is extended in CD-graph to express different scales of spatial adjacency and neighbourhood relation of objects. CD-graph can be widely used in geographical applications, such as spatial interpolation, spatial clustering and spatial decision support.

Keywords:

• CD-graph
• spatial adjacency
• spatial neighbourhood relation
• constrained Delaunay triangulation
• Voronoi diagram

Acknowledgements

This work is supported by the National Science Foundation of China under Grants 30972299 and 41001203, by EC FP7‐2009-People-IRSES under Grant 247608, and by Fujian Sci. & Tech. program under Grants 2010I0008 and 2010HZ0004‐1. We express our thanks to Mr. Hongyu Huang for improving the readability of this article.