A distributed triangulation algorithm for wireless sensor networks on 2D and 3D surface

Triangulation serves as the basis for many geometry-based algorithms in wireless sensor networks. In this paper we propose a distributed algorithm that produces a triangulation for an arbitrary sensor network, with no constraints on communication model or granularity of the triangulation. We prove its correctness in 2D, and further extend it to sensor networks deployed on 3D open and closed surfaces. Our 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.