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

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!

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$.

• Thanks very much for your help and detailed answer! [+1] – Ryan Jun 8 '18 at 14:36
• Hmm... It seems that for $d = 3$ and $n = 2$, $3n-6 = 0$ cannot reflect the minimum number of edges. – Ryan Jun 8 '18 at 14:44
• In that case, there's a motion that fixes the points - around the axis. Therefore, the Euclidean motions have fewer degrees of freedom. You need the vectors between the points to span $\mathbb{R}^d$ for these formulas to apply. – Michael Burr Jun 8 '18 at 15:40
• Thanks a lot! [+1] It seems that spanning vectors in ${\mathbb R}^{d-1}$ is sufficient for applying these formulae :-) – Ryan Jun 11 '18 at 3:06
• Note that these conditions are necessary, but not sufficient, even in the spanning case. – Michael Burr Jun 11 '18 at 4:03