Book chapter
On the Efficiency of a Local Iterative Algorithm to Compute Delaunay Realizations
Experimental Algorithms, pp.69-86
Lecture Notes in Computer Science, Springer Berlin Heidelberg
2008
DOI: 10.1007/978-3-540-68552-4_6
Abstract
Greedy routing protocols for wireless sensor networks (WSNs) are fast and efficient but in general cannot guarantee message delivery. Hence researchers are interested in the problem of embedding WSNs in low dimensional space (e.g., ℝ2) in a way that guarantees message delivery with greedy routing. It is well known that Delaunay triangulations are such embeddings. We present the algorithm FindAngles, which is a fast, simple, local distributed algorithm that computes a Delaunay triangulation from any given combinatorial graph that is Delaunay realizable. Our algorithm is based on a characterization of Delaunay realizability due to Hiroshima et al. (IEICE 2000). When compared to the PowerDiagram algorithm of Chen et al. (SoCG 2007), our algorithm requires on average 1/7th the number of iterations, scales better to larger networks, and has a much faster distributed implementation. The PowerDiagram algorithm was proposed as an improvement on another algorithm due to Thurston (unpublished, 1988). Our experiments show that on average the PowerDiagram algorithm uses about 18% fewer iterations than the Thurston algorithm, whereas our algorithm uses about 88% fewer iterations. Experimentally, FindAngles exhibits well behaved convergence. Theoretically, we prove that with certain initial conditions the error term decreases monotonically. Taken together, these suggest our algorithm may have polynomial time convergence for certain classes of graphs. We note that our algorithm runs only on Delaunay realizable triangulations. This is not a significant concern because Hiroshima et al. (IEICE 2000) indicate that most combinatorial triangulations are indeed Delaunay realizable, which we have also observed experimentally.
Details
- Title: Subtitle
- On the Efficiency of a Local Iterative Algorithm to Compute Delaunay Realizations
- Creators
- Kevin M. Lillis - Saint Ambrose UniversitySriram V. Pemmaraju - University of Iowa
- Resource Type
- Book chapter
- Publication Details
- Experimental Algorithms, pp.69-86
- Publisher
- Springer Berlin Heidelberg; Berlin, Heidelberg
- Series
- Lecture Notes in Computer Science
- DOI
- 10.1007/978-3-540-68552-4_6
- eISSN
- 1611-3349
- ISSN
- 0302-9743
- Language
- English
- Date published
- 2008
- Academic Unit
- Computer Science
- Record Identifier
- 9984259438002771
Metrics
5 Record Views