Distributed Gabriel Graph Construction and Meta-Information Gathering

Gabriele Oliva, Roberto Setola, Marios Polycarpou

Abstract

In this paper we provide a distributed way to transform the network topology underlying a set of agents embedded in a bi-dimensional space into a planar graph, and specifically into a Gabriel graph. Moreover, a distributed algorithm based on synchronized consensus methodologies is provided in order to gather some useful pieces of meta-information (number of faces, average size of the faces, size of the boundary, etc.) and to let each node in the Gabriel graph identify its “role" (i.e., node that links two subgraphs, node on a branch ending with a leaf, node belonging to a face, etc.). The insights obtained by means of the proposed approach may contribute to develop better geographic routing techniques as well as to improve the local decision capability of the agents in distributed environments.

Keywords

Gabriel Graphs, Planar Graphs, Synchronized Consensus Algorithms

Download

IMEKO-TC4-2014-314.pdf

DOI

-

IMEKO TC

TC4 - Measurement of Electrical Quantities

Back to the proceedings