Combinatorial decomposition, generic independence and algebraic complexity of geometric constraints systems: applications in biology and engineering
Meera Sitharam, Yong Zheng Zhou · 2006
This dissertation contributes to 7 problems in geometric constraints solving and applications. We study the problem of enabling general 2D and 3D variational constraint representation to be used in conjunction with a feature hierarchy representation, where some of the features may use procedural or other non-constraint based representations. We give a combinatorial approximate characterization of such graphs which we call module-rigidity, which can be determined by a polynomial time algorithm. The new method has been implemented in the FRONTIER and has many useful properties and practical applications. We propose a combinatorial characterization conjecture of 2D rigidity of angle constraint system. We give the formal statement of generically independence. We are trying to prove it use induction on the number of points. Three of four cases have been proved. We also study the well-documented problem of systematically navigating the potentially exponentially many roots or realizations of well-constrained, variational geometric constraint systems. We give a scalable method called the ESM or Equation and Solution Manager that can be used both for automatic searches and visual, user-driven searches for desired realizations. We also show that, especially for 3D geometric constraint systems, a further optimization of the algebraic complexity of the subsystems is both possible, and often necessary to solve the well-constrained systems selected by the DR-plan. We give an efficient algorithm to optimize the algebraic complexity of the well-formed system that is constructed by the algorithm given by Sitharam. We implement a randomized algorithm to compute one measure of the probability of the pathways and prospect to incorporate another probability measure, that will be obtained combinatorially by extending Hendricksons Theorem on rigidity circuits and unique graph realization into this algorithm.