Date Added: Jan 2011
Triangulation serves as the basis for many geometry based algorithms in wireless sensor networks. In this paper, the authors propose a distributed algorithm that produces a triangulation for an arbitrary sensor network, with no constraints on communication model or granularity of the triangulation. They prove its correctness in 2D, and further extend it to sensor networks deployed on 3D open and closed surfaces. Their simulation results show that the proposed algorithms can tolerate distance measurement errors, and thus work well under practical sensor network settings and effectively promote the performance a range of applications that depend on triangulations.