Spatial geometric constraint solving based on k-connected graph decomposition
Guifang Zhang, Xiaoshan Gao · 2006
We propose a geometric constraint solving method based on connectivity analysis in graph theory, which can be used to decompose a well-constrained problem into some smaller ones if possible. We also show how to merge two rigid bodies if they share two or three geometric primitives in a bi-connected or tri-connected graph respectively. Based on this analysis, problems similar to the "double banana problem" could be easily detected.