4
$\begingroup$

Given a graph $G=(V,E)$ and a length function $\ell:E\to\mathbb{R}_+$. An embedding of the graph into the $d$-dimensional Euclidean space is a map $f:V\to\mathbb{R}^d$ such that $||f(u)-f(v)||=\ell(uv)$ if $uv\in E$. (So $(G,f)$ is actually a framework in terms of rigidity theory.)

I'm thinking about finding an embedding that maximize the volume of the convex hull of the point set $\{f(v)\mid v\in V\}$ in $\mathbb{R}^d$ (the dimension in question is fixed).

Of course, we should assume the existence of an embedding, and that the framework is not globally rigid, otherwise the answer is trivial.

Example

let $G$ be a $m\times n$ grid graph, $\ell=1$ and $d=2$. Then the embedding maximizing the volume is the canonical one: part of the square lattice.

Improve this question
$\endgroup$
5
  • $\begingroup$ any one tell me how to type the braket {} for a set? \{ \} doesn't work. $\endgroup$
    – Hao Chen
    Mar 18, 2013 at 13:56
  • $\begingroup$ Use double backslashes \\{ \\} $\endgroup$
    – Bati
    Mar 18, 2013 at 15:11
  • 1
    $\begingroup$ A volume maximizing embedding always exists because the space of embeddings is compact. $\endgroup$
    – David Cohen
    Mar 18, 2013 at 16:09
  • 1
    $\begingroup$ @David Cohen: Yes of course. But we need to assume that an embedding exists at the first place. I mean, situation like $G=C_3$ (triangle), $\ell=3,4,10$ should not be considered. $\endgroup$
    – Hao Chen
    Mar 18, 2013 at 17:45
  • $\begingroup$ I believe I can see how to show that minimizing the volume is NP-hard, and I suspect that maximizing is equally difficult. $\endgroup$
    – Joseph O'Rourke
    Mar 19, 2013 at 1:10

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.