Physics – Computational Physics
Scientific paper
1996-12-27
J. Phys. A: Math. Gen. 29 (1996), 8097
Physics
Computational Physics
LaTeX, 18 pages, 10 eps figures
Scientific paper
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.
No associations
LandOfFree
An efficient algorithm for two-dimensional central-force rigidity does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with An efficient algorithm for two-dimensional central-force rigidity, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An efficient algorithm for two-dimensional central-force rigidity will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-702496