How to determine the minimum number of edges to form a rigid structure in ${\mathbb R}^d$ ($d = 2,3$)?

Question

Let $x_1,\ldots,x_n$ be $n$ points in ${\mathbb R}^d$ ($d = 2,3$). Then, what is the minimum number of edges to form a rigid structure?

Thanks!

Answer 1

See Laman's Theorem for $\mathbb{R}^2$. The case for $\mathbb{R}^3$ is more complicated - see the double banana.

If you want a lower bound, take the number of degrees of freedom of the points and subtract the dimension of the Euclidean group. This works because each edge can remove one degree of freedom. However, having this number of edges doesn't guarantee that the structure is rigid.

In $\mathbb{R}^d$, each point has $d$ degrees of freedom, and the Euclidean group has dimension $\frac{d(d+1)}{2}$. Therefore, the minimum number of edges required is $dn-\frac{d(d+1)}{2}$. Therefore, in $\mathbb{R}^2$, the number of edges required is $2n-3$ and in $\mathbb{R}^3$, the number of edges required is $3n-6$.

This argument requires that nontrivial subgroups of the Euclidean group do not stabilize the set, so we must assume that the vectors between the points span $\mathbb{R}^d$.