Triangulations are rigid. You can do better using pseudo-triangles

Triangles are, definitely, among the most used mathematical objects. One of the reasons is that they are simple (actually the smallest polygon). Another very important reason is that they are rigid, which is the property behind the many structures composed by triangles we can see in our daily life.

Credit: David Orden
Credit: David Orden

But, surprisingly enough, triangulations are not the 2D rigid structures with fewest bars. Such structures are the so-called pointed pseudo-triangulations.

Pseudo-triangles generalize the notion of triangle by allowing its sides to be, instead of a single segment, a polygonal chain with the property of being inner convex. Hence, triangles are just a particular, “straight”, type of pseudo-triangles.

Credit: David Orden
Credit: David Orden

Thus, a pseudo-triangulation of a point set is a tessellation of its convex hull by pseudo-triangles. Further, a pseudo-triangulation is said to be pointed if all the vertices are incident to an angle greater than 180 degrees (\pi for the sweet ones). The following figure shows, for the same set of points, a triangulation (left) and a pointed pseudo-triangulation (right).

Credit: David Orden
Credit: David Orden

It is apparent that pointed pseudo-triangulations have fewer edges than triangulations. Actually, Streinu 1 showed that for n points a pseudo-triangulation has 2n-3+x edges, with x being the number of non-pointed vertices. In particular, a pointed pseudo-triangulation has 2n-3 edges, while a triangulation has 2n-3+(n-h)=3n-3-h edges, for h being the number of hull points of the set (the only pointed ones in a triangulation).

Back to rigidity, and informally speaking, we can say that a structure is rigid if any movement either breaks the structure or moves the structure as a whole. For an example, a triangle is rigid while a pseudo-triangle might not be rigid; the following figure (right) shows a movement which neither breaks the pseudo-triangle nor moves it as a whole.

Credit: David Orden
Credit: David Orden

Streinu also proved that, nicely enough considering the previous example, pointed pseudo-triangulations are rigid. The left picture in the following figure shows that the previous movement now will move the pointed pseudo-triangulation as a whole, as any other movement will do. (Remember that we are working in 2D, so that 3D movements are not allowed.) The reader can figure out the same property for the larger pointed pseudo-triangulation in the right picture.

Credit: David Orden
Credit: David Orden

This implies that, in order to construct a rigid 2D structure, pointed pseudo-triangulations allow to get rid of many bars with respect to triangulations. In particular, as we have seen above, a pointed pseudo-triangulation will use only 2n-3 bars, instead of the 2n-3+(n-h) bars used by a triangulation.

Streinu also proved that pointed pseudo-triangulations are, in fact, minimally rigid. That is, removing any edge would destroy the rigidity. This is very close to proving that 2n-3 is the smallest number of bars we can use for a rigid 2D structure… except that we have to make sure that there are no other minimally rigid structures.

This was precisely the result by Haas et al.2. There we proved that, if a structure is minimally rigid, then it has to be a pointed pseudo-triangulation. More precisely, if an abstract graph is planar (2D structures have no crossings) and minimally rigid, then it can be geometrically embedded as a pointed-pseudo-triangulation.

Interestingly enough, abstract graphs being minimally rigid can be characterized in a purely combinatorial way. Just counting vertices and edges! Laman3 proved that a graph with n vertices is minimally rigid if, and only if, (i) it has 2n-3 edges and (ii) every subgraph with \tilde{n}\geq 2 vertices has at most 2\tilde{n}-3 edges.

An equivalent way of characterizing the graphs with this property is, as proved by Tay and Whiteley 4, the Henneberg construction 5:

Start with an edge joining two vertices. At each step, add a new vertex in one of these two ways:

  • Henneberg I (vertex addition): insert a new vertex and connect it to two old vertices, using two new edges.

  • Henneberg II (edge splitting): insert a new vertex on an old edge, which gets split into two new edges, and connect the new vertex to a third old vertex, using one new edge.

Credit: Haas et al (2005)
Credit: Haas et al (2005)

Our first proof technique, of a local nature, shows that there are geometric placements of the points in this abstract Henneberg which result in an embedding of the minimally rigid planar graph meeting the conditions a pointed pseudo-triangulation (pointedness and pseudo-triangles as faces).

Haas et al (2005)
Haas et al (2005)

Our second proof technique, of a global nature, makes use of a directed version of Tutte’s barycentric embedding 6, adapted to produce pointed-pseudo-triangulations instead of convex faces.

Both proofs yield efficient embedding algorithms and allow to obtain some stronger results, using a combinatorial abstraction of pseudo-triangulations. These combinatorial pseudo-triangulations are defined as topological plane embeddings of a graph, together with an assignment of angles which mimics the properties of geometric pseudo-triangulations.

Using this notion, part of the authors of [2] could further generalize the previous results to general rigidity and pseudo-triangulations 7. Actually, we showed that the rigidity of planar graphs can be stratified according to the number of non-pointed vertices in an associated combinatorial pseudo-triangulation.

In summary, apart from having other interesting properties, pseudo-triangulations provide a missing link between planarity and rigidity in geometric graph theory.

References

  1. Ileana Streinu. A combinatorial approach to planar non-colliding robot arm motion planning. In Proceedings of the 41st Annual Symposium on Foundations of Computer Science (2000), pages 443-453. DOI: http://dx.doi.org/10.1109/SFCS.2000.892132
  2. Ruth Haas, David Orden, Günter Rote, Francisco Santos, Brigitte Servatius, Herman Servatius, Diane Souvaine, Ileana Streinu, and Walter Whiteley. Planar minimally rigid graphs and pseudo-triangulations. Computational Geometry: Theory and Applications, 31:1-2 (2005), pages 31-61. DOI: http://dx.doi.org/10.1016/j.comgeo.2004.07.003
  3. Gerard Laman. On graphs and rigidity of plane skeletal structures. Journal of Engineering Mathematics 4:4 (1970), pages 331-340. DOI: http://dx.doi.org/10.1007/BF01534980
  4. Tiong-Seng Tay and Walter Whiteley. Generating isostatic graphs. Structural Topology 11 (1985), pages 21–68. http://www-iri.upc.es/people/ros/StructuralTopology/WholeIssues/st11-ocr.pdf
  5. Lebrecht Henneberg. Die graphische Statik der starren Systeme, Leipzig, 1911, Johnson Reprint 1968. https://archive.org/details/diegraphischest00henngoog
  6. William Thomas Tutte. How to draw a graph. Proceedings of the London Mathematical Society, s3-13:1 (1963), pages 743-767. DOI: http://dx.doi.org/10.1112/plms/s3-13.1.743
  7. David Orden, Francisco Santos, Brigitte Servatius, and Herman Servatius. Combinatorial pseudo-triangulations. Discrete Mathematics, 307 (2007), pages 554-566. DOI: http://dx.doi.org/10.1016/j.disc.2005.09.045

Written by

2 comments

Leave a Reply

Your email address will not be published.Required fields are marked *