Files:
(unavailable)
Abstract:
A graph $G$ is called generically minimally rigid in $\RR^d$ if, for any choice of sufficiently generic edge lengths, it can be embedded in $\RR^d$ in a finite number of distinct ways, modulo rigid transformations. Here, we deal with the problem of determining tight bounds on the number of such embeddings, as a function of the number of vertices. The study of rigid graphs is motivated by numerous applications, mostly in robotics, bioinformatics, and architecture. We capture embeddability by polynomial systems with suitable structure, so that their mixed volume, which bounds the number of common roots, yields interesting upper bounds on the number of embeddings. We explore different polynomial formulations so as to reduce the corresponding mixed volume, namely by introducing new variables that remove certain spurious roots, and by applying the theory of distance geometry. We focus on $\RR^2$ and $\RR^3$, where Laman graphs and 1-skeleta of convex simplicial polyhedra, respectively, admit inductive Henneberg constructions. Our implementation yields upper bounds for $n łe 10$ in $\RR^2$ and $\RR^3$, which reduce the existing gaps and lead to tight bounds for $nłe 7$ in both $\RR^2$ and $\RR^3$; in particular, we describe the recent settlement of the case of Laman graphs with 7 vertices. We also establish the first lower bound in $\RR^3$ of about $2.52^n$, where $n$ denotes the number of vertices.
BibTeX:
@InCollection{etv-dg-2012,
author = {Ioannis~Z. Emiris and Elias~P. Tsigaridas and
Antonios Varvitsiotis},
title = {Mixed volume and distance geometry techniques for
counting Euclidean embeddings of rigid graphs},
booktitle = {Distance Geometry: With Applications to Molecular
Conformation and Sensor Networks},
editor = {C.~Lavor and L.~Liberti and N.~Maculan and
A.~Mucherino},
publisher = {Springer-Verlag},
year = 2012,
edition = "(To appear)",
chapter = "XX)",
abstract = "A graph $G$ is called generically minimally rigid in
$\RR^d$ if, for any choice of sufficiently generic
edge lengths, it can be embedded in $\RR^d$ in a
finite number of distinct ways, modulo rigid
transformations. Here, we deal with the problem of
determining tight bounds on the number of such
embeddings, as a function of the number of vertices.
The study of rigid graphs is motivated by numerous
applications, mostly in robotics, bioinformatics,
and architecture. We capture embeddability by
polynomial systems with suitable structure, so that
their mixed volume, which bounds the number of
common roots, yields interesting upper bounds on the
number of embeddings. We explore different
polynomial formulations so as to reduce the
corresponding mixed volume, namely by introducing
new variables that remove certain spurious roots,
and by applying the theory of distance geometry. We
focus on $\RR^2$ and $\RR^3$, where Laman graphs and
1-skeleta of convex simplicial polyhedra,
respectively, admit inductive Henneberg
constructions. Our implementation yields upper
bounds for $n \le 10$ in $\RR^2$ and $\RR^3$, which
reduce the existing gaps and lead to tight bounds
for $n\le 7$ in both $\RR^2$ and $\RR^3$; in
particular, we describe the recent settlement of the
case of Laman graphs with 7 vertices. We also
establish the first lower bound in $\RR^3$ of about
$2.52^n$, where $n$ denotes the number of vertices."
}
Generated by bib2html.pl (written by Patrick Riley , modified by Elias ) on Wed Oct 23, 2019 21:41:02