The aim is to develop a key, missing technology for flexible decomposition of geometric constraint systems into small, compact subsystems whose solutions can be recombined. Due to the current lack of such decomposition-recombination techniques,
This basic inadequacy in spatial constraint solving seriously hinders progress in the development of intelligent CAD/CAM/CAE systems.
Initial research (see recent paper) has uncovered a new and efficient approach for isolating small, solvable subsets of geometric constraint systems. The approach is based on a simple but unconventional modification of network flow. It is completely general, handles all constraint systems, is easy to implement as well as to modularize and hence has the potential to become the key component of a new generation of constraint solvers in CAD/CAM/CAE systems. The decomposition technology to be developed by the proposed project will be based on this recent break-through. Applications would extend to all contexts where geometric constraints arise, including virtual reality, graphics, robotics, teaching geometry, etc.
The decomposition problem has geometric, algebraic as well as graph-theoretic components, and consists of three broadly defined subproblems:
We will continue to perform rigorous complexity analyses on the new algorithms as well as develop prototype implementations. To assess the practicality of the prototypes, we will compare them with benchmarks, both in terms of stand-alone performance, and the ease of incorporation as modular components into existing geometric constraint solvers.