Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
any one tell me how to type the braket {} for a set? \{ \} doesn't work. –  Hao Chen Mar 18 '13 at 13:56
    
Use double backslashes \\{ \\} –  Bati Mar 18 '13 at 15:11
1  
A volume maximizing embedding always exists because the space of embeddings is compact. –  David Cohen Mar 18 '13 at 16:09
1  
@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. –  Hao Chen Mar 18 '13 at 17:45
    
I believe I can see how to show that minimizing the volume is NP-hard, and I suspect that maximizing is equally difficult. –  Joseph O'Rourke Mar 19 '13 at 1:10

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.