Distributed computation of virtual coordinates

Mirela Ben Chen, Craig Gotsman, Camille Wormser

Research output: Chapter in Book/Report/Conference proceedingConference contribution

27 Scopus citations


Sensor networks are emerging as a paradigm for future computing, but pose a number of challenges in the fields of networking and distributed computation. One challenge is to devise a greedy routing protocol - one that routes messages through the network using only information available at a node or its neighbors. Modeling the connectivity graph of a sensor network as a 3-connected planar graph, we describe how to compute on the network in a distributed and local manner a special geometric embedding of the graph. This embedding supports a geometric routing protocol based on the "virtual" coordinates of the nodes derived from the embedding.

Original languageEnglish (US)
Title of host publicationProceedings of the Twenty-third Annual Symposium on Computational Geometry, SCG'07
Number of pages10
StatePublished - 2007
Externally publishedYes
Event23rd Annual Symposium on Computational Geometry, SCG'07 - Gyeongju, Korea, Republic of
Duration: Jun 6 2007Jun 8 2007

Publication series

NameProceedings of the Annual Symposium on Computational Geometry


Other23rd Annual Symposium on Computational Geometry, SCG'07
Country/TerritoryKorea, Republic of

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Mathematics


  • Distributed computing
  • Greedy routing
  • Planar embedding
  • Power diagrams
  • Virtual coordinates


Dive into the research topics of 'Distributed computation of virtual coordinates'. Together they form a unique fingerprint.

Cite this