University of Illinois Urbana-Champaign

Distributed Algorithms for Voronoi Diagrams and Applications in Ad-hoc Networks

Hadjicostis, Christoforos N.; Cao, Min

Content Files
UILU-ENG-03-2222_DC-210.pdf

Permalink

https://hdl.handle.net/2142/99588

Description

Title
Distributed Algorithms for Voronoi Diagrams and Applications in Ad-hoc Networks
Author(s)
  • Hadjicostis, Christoforos N.
  • Cao, Min
Issue Date
2003-10
Keyword(s)
  • Voronoi diagram
  • Distributed algorithms
  • Ad-hoc networks
  • Ad hoc networks
  • Topology control
Date of Ingest
2018-04-03T16:47:22Z
Abstract
The Voronoi diagram is a fundamental structure in computational geometry and arises naturally in many applications including wireless networking. In this paper, we propose a distributed algorithm by which each node u can compute its Voronoi region in O(d(u)) time, where d(u) is the number of the Voronoi neighbors of node u. Then we show how the algorithm can be applied in topology control of wireless ad-hoc networks, and also propose a revised version of the algorithm to minimize transmission energy consumption. Further applications of the algorithm in different areas are expected.
Publisher
Coordinated Science Laboratory, University of Illinois at Urbana-Champaign
Series/Report Name or Number
Coordinated Science Laboratory Report no. UILU-ENG-03-2222, DC-210
Type of Resource
text
Genre of Resource
Technical Report
Language
en
Permalink
http://hdl.handle.net/2142/99588
Sponsor(s)/Grant Number(s)
National Science Foundation

Owning Collections

Report - Coordinated Science Laboratory PRIMARY