dorsal/arxiv
View SchemaAn efficient algorithm for two-dimensional central-force rigidity
| Authors | Cristian F. Moukarzel |
|---|---|
| Categories | |
| ArXiv ID | physics/9612013 |
| URL | https://arxiv.org/abs/physics/9612013 |
| Journal | J. Phys. A: Math. Gen. 29 (1996), 8097 |
Abstract
Given a structure made up of n sites connected by b bars, the problem of recognizing which subsets of sites form rigid units is not a trivial one, because of the non-local character of rigidity in central-force systems. Even though this is a very old problem of statics, no simple algorithms are available for it so the most usual approach has been to solve the elastic equations, which is very time-consuming for large systems. Recently an integer algorithm was proposed for this problem in two dimensions, using matching methods from graph theory and Laman's theorem for two-dimensional graphs. The method is relatively simple, but its time complexity grows as $n^2$ in the worst case, and almost as fast on practical cases, so that an improvement is highly desirable. I describe here a further elaboration of that procedure, which relies upon the description of the system as a collection of rigid bodies connected by bars, instead of sites connected by bars. Sets of rigidly connected objects are replaced by a unique body, and this is done recursively as more rigid connections between bodies are discovered at larger scales. As a consequence of this ``rescaling transformation'', our algorithm has much improved average behavior, even when its worst-case complexity remains $n^2$. The time complexity of the body-bar algorithm is found to scale as $n^{1.12}$ for the randomly diluted triangular lattice, while the original site-bar version scales as $n^{1.9}$ on the same problem.
{
"annotation_id": "f07e8aba-cbf0-44a7-8e6c-ddf954a9ae31",
"date_created": "2026-03-02T18:01:17.807000Z",
"date_modified": "2026-03-02T18:01:17.807000Z",
"file_hash": "e7a0cc797fac0fbc8f450e5dfdb8856e3cfb0d4d8de41c7756125ce1cd412fce",
"private": false,
"record": {
"abstract": "Given a structure made up of n sites connected by b bars, the problem of\nrecognizing which subsets of sites form rigid units is not a trivial one,\nbecause of the non-local character of rigidity in central-force systems. Even\nthough this is a very old problem of statics, no simple algorithms are\navailable for it so the most usual approach has been to solve the elastic\nequations, which is very time-consuming for large systems. Recently an integer\nalgorithm was proposed for this problem in two dimensions, using matching\nmethods from graph theory and Laman\u0027s theorem for two-dimensional graphs. The\nmethod is relatively simple, but its time complexity grows as $n^2$ in the\nworst case, and almost as fast on practical cases, so that an improvement is\nhighly desirable. I describe here a further elaboration of that procedure,\nwhich relies upon the description of the system as a collection of rigid bodies\nconnected by bars, instead of sites connected by bars. Sets of rigidly\nconnected objects are replaced by a unique body, and this is done recursively\nas more rigid connections between bodies are discovered at larger scales. As a\nconsequence of this ``rescaling transformation\u0027\u0027, our algorithm has much\nimproved average behavior, even when its worst-case complexity remains $n^2$.\nThe time complexity of the body-bar algorithm is found to scale as $n^{1.12}$\nfor the randomly diluted triangular lattice, while the original site-bar\nversion scales as $n^{1.9}$ on the same problem.",
"arxiv_id": "physics/9612013",
"authors": [
"Cristian F. Moukarzel"
],
"categories": [
"physics.comp-ph",
"math-ph",
"math.MP"
],
"journal_ref": "J. Phys. A: Math. Gen. 29 (1996), 8097",
"title": "An efficient algorithm for two-dimensional central-force rigidity",
"url": "https://arxiv.org/abs/physics/9612013"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "478d6788-27c6-440b-b023-ee24f19d58ee",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}