A Distributed Greedy Heuristic for Computing Voronoi Tessellations with Applications Towards Peer-to-Peer Networks
Authors:
- Brendan BenshoofBBBrendan Benshoof
- Andrew RosenARAndrew Rosen
- Anu G. BourgeoisABAnu G. Bourgeois
- Robert W. HarrisonRHRobert W. Harrison
- 1 May 2015
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1089-1096
Abstract
Computing Voronoi tessellations in an arbitrary number of dimensions is a computationally difficult task. This problem becomes exacerbated in distributed environments, such as Peer-to-Peer networks and Wireless networks, where Voronoi tessellations have useful applications. We present our Distributed Greedy Voronoi Heuristic, which approximates Voronoi tessellations in distributed environments. Our heuristic is fast, scalable, works in any geometric space with a distance and midpoint function, and has interesting applications in embedding metrics such as latency in the links of a distributed network.Keywords
This publication has 17 references indexed in Scilit:
- Voronoi-Based Sleeping Configuration in Wireless Sensor Networks with Location Error2008
- Distributed and dynamic voronoi overlays for coverage detection and distributed hash tables in ad-hoc networks2004
- Scalable peer-to-peer networked virtual environment2004
- Kademlia: A Peer-to-Peer Information System Based on the XOR Metric2002
- GHT2002
- Pastry: Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-to-Peer Systems2001
- A scalable content-addressable network2001
- Chord2001
- Triangle: Engineering a 2D quality mesh generator and Delaunay triangulator1996
- THE EXPECTED EXTREMES IN A DELAUNAY TRIANGULATIONInternational Journal of Computational Geometry & Applications, 1991