|
A $d$-dimensional bar-and-joint framework $(G,p)$, where $G$ is a graph and
$p$ maps the vertices of $G$ to points in $\R^d$, is said to be
globally rigid if every $d$-dimensional framework $(G,q)$ with the same graph and same edge
lengths is congruent to $(G,p)$.
Global rigidity of frameworks and graphs is a well-studied area of rigidity
theory with a number of applications, including the localization problem of
sensor networks.
Motivated by this application we consider the new notion of unit ball global
rigidity, which can be defined similarly, except that
$(G,p)$ as well as $(G,q)$ are required to be unit ball frameworks in the
above definition. In a unit ball framework two vertices are adjacent if and
only if their distance is less than a fixed constant (which corresponds to the sensing
radius in a sensor network).
In this paper we initiate a theoretical analysis of this version of global
rigidity and prove several structural results. Among others we identify
families of frameworks (and corresponding graphs $G$) in $\R^d$, for all
$d\geq 1$, which are unit ball
globally rigid without being
globally
rigid in the usual sense.
These families contain minimally rigid graphs, too, which have less edges than
any of the globally rigid graphs on the same number of vertices.
Bibtex entry:
| AUTHOR | = | {Garamvölgyi, D{\'a}niel and Jord{\'a}n, Tibor}, |
| TITLE | = | {Global Rigidity of Unit Ball Graphs}, |
| NOTE | = | {{\tt egres.elte.hu}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2018}, |
| NUMBER | = | {TR-2018-17} |