Menu
Delaunay graphs have been used in CAD/CAM, sensor networks, and geographic information systems. We investigate the reliability properties of nodes in Delaunay graphs. For measuring the reliability, we formulate the concept of roaming-region for nodes. The \emph{roaming-region} \( R(i) \) of a Delaunay node \( v_i \) is such that the Delaunay graph does not change as long as \( v_i \) remains within \( R(i) \). A node \( v_i \) with a large roaming region \( R(i) \) such that \( v_i \) is positioned near the center of \( R(i) \) is identified as a reliable node. Two types of roaming regions called (i) \emph{lateral roaming region} \( LR(i) \) and (ii) \emph{radial roaming region} \( RR(i) \) are distinguished to develop the algorithm. The roaming region itself is expressed as the intersection of \( RR(i) \) and \( LR(i) \). For nodes inside the convex hull, called \emph{deep internal nodes}, we present an \( O(n^2) \) time algorithm for computing their roaming region, where \( n \) is the number of nodes in the Delaunay triangulation. We finally discuss generalization and extension of the proposed algorithm.