EMI: An Efficient Algorithm for Identifying Maximal Rigid Clusters in 3D Generic Graphs

doi:10.1109/TNET.2023.3287822

2024-02-01

PRE

Qinhan Wei

Yongcai Wang *

李德英 (Deying Li)

DOI：10.1109/TNET.2023.3287822

原文链接

原文求助

摘要

En 中文

Identifying the Maximal Rigid subGraphs (MRGs) whose relative formations cannot deform continuously in R-d, is a fundamental problem in network formation control and network localization. When d = 3, it becomes extremely challenging and has been open for decades because the fundamental Laman condition doesn't hold in R-3. This paper presents a new understanding of this problem. Because of the existence of implicit hinges in 3D, its essence should be to detect the Maximal Rigid Clusters (MRCs). An MRC is a maximal set of vertices in which each vertex is mutually rigid to the others, but the vertices are not necessarily connected. We show that the MRGs in the original graph can be easily deduced from the connected components generated by the MRCs. For efficiently identifying the MRCs, at first, a randomized algorithm to detect mutually rigid vertex pairs is exploited. Based on this, a Basic MRC Identification algorithm (BMI) is proposed, which is an exact algorithm that can detect all MRCs based on the extracted rigid vertex pairs, but it has O(|V|(4)) time complexity. To further pursue an efficient algorithm, we observe the hinge MRCs appear rarely. So an Efficient framework for MRC Identification (EMI) is proposed. It consists of two steps: 1) a Trimmed-BMI algorithm that guarantees to detect all simple MRCs and may miss only hinge MRCs; 2) a Trim-FIX algorithm that can find all hinge MRCs. We prove EMI can guarantee to detect all the MRCs as accurately as BMI, using O(|V|(3)) times. Further, we show EMI achieves magnitudes of times faster than BMI in experiments. Extensive evaluations verify the effectiveness and high efficiency of EMI in various 3D networks. We have uploaded the code of the related program to https://github.com/fdwqh/EMI-algorithm.

Keyword:

Maximum rigid cluster partition

3D networks

rigid cluster

implicit hinge

mutual rigid pair