Contents

-

Roaming Regions for Delaunay Nodes

Laxmi P Gewali1, Romas Hada1
1University of Nevada, Las Vegas

Abstract

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 vi is such that the Delaunay graph does not change as long as vi remains within R(i). A node vi with a large roaming region R(i) such that vi 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(n2) 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.