Constraint Solving with Geometric Transformation 53

Abstract. This paper proposes two algorithms for solving geometric constraint systems. The first algorithm is for constrained systems without loops and has linear complexity. The second algorithm can solve constraint systems with loops. This algorithm is of quadratic complexity and is complete for constraint problems about simple polygons. The key of the algorithm is to combine the idea of graph based methods for geometric constraint solving and geometric transformations coming from rule-based methods. 1