An Efficient Algorithm for the Shortest Path in the Delaunay Triangulation

The goal of the current article is to optimize the time complexity to find new points in the Delaunay Triangulation. Adding these points to the triangulated set in the current Delaunay triangulation, the shortest path between two nodes in the new Delaunay triangulation has improved. Regarding the position of these points in the intersection of Delaunay circles, we present a sweep line algorithm to find the intersection points between the Delaunay circles. This algorithm has optimal time complexity using two techniques. First, one can see that intersection of the two circles is not calculated when they are distinct. Second, after finding the intersection points of a circle with other circles, that circle is removed from the algorithm calculations cycle. In conclusion the time complexity of our algorithm equals with the number of intersection of Delaunay circles and is optimal regardless of the additional calculation. Considering to the applications of Delaunay triangulation in geometric routing protocol in Wireless Sensor Networks, new sensors can be placed on the points that calculated by our algorithm and improve the shortest path between two sensors, so increase the data transfer speed in Wireless Sensor Networks

Keywords:

Circle intersection , Delaunay triangulation , Geometric routing , Wireless Sensor Network